fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define pb push_back
  5. #define myPair pair<int,int>
  6. #define mp make_pair
  7. #define fi first
  8. #define se second
  9. #define qmax priority_queue<int>
  10. #define qmin priority_queue<int,vector<int>,greater<int>>
  11. #define all(x) x.begin(),x.end()
  12. #define FOR(i,a,b) for(int i = a; i <= b; i++)
  13. #define FORR(i,a,b) for(int i = a; i >= b; i--)
  14.  
  15. const int mxn = 1e6 + 10;
  16. vector<int> g[mxn];
  17. int n, r, m;	// number of vertices, edges and soldiers respectively
  18. int color[mxn];
  19. vector<pair<int,int>> sol;
  20. bool flag;
  21.  
  22. void dfs(int u, int par, int level, int k)
  23. {
  24. 	if(level == k + 1)
  25. 		return;
  26.  
  27. 	color[u] = 1;
  28. 	for(int v : g[u]) {
  29. 		if(v == par)
  30. 			continue;
  31. 		if(!color[v])
  32. 			dfs(v, u, level + 1, k);
  33. 		else if(color[v] && level != k)
  34. 			flag = 0;
  35. 	}
  36. }
  37.  
  38. void solve()
  39. {
  40. 	cin >> n >> r >> m;
  41. 	FOR(i, 1, n) {
  42. 		g[i].clear();
  43. 	}
  44. 	sol.clear();
  45. 	FOR(i, 1, r) {
  46. 		int u, v;	cin >> u >> v;
  47. 		g[u].pb(v);
  48. 		g[v].pb(u);
  49. 	}
  50. 	FOR(i, 1, m) {
  51. 		int a, b;	cin >> a >> b;
  52. 		sol.pb(mp(a, b));	// city number and soldier's strength
  53. 	}
  54. 	memset(color, 0, sizeof(color));
  55.  
  56. 	flag = 1;
  57. 	for(auto it : sol)
  58. 	{
  59. 		int city = it.fi;
  60. 		if(!color[city])
  61. 			dfs(city, -1, 0, it.se);
  62. 		else if(color[city]) {
  63. 			flag = 0;
  64. 			break;
  65. 		}
  66. 	}
  67.  
  68. 	FOR(i, 1, n) {
  69. 		if(!color[i]) {
  70. 			flag = 0;
  71. 			break;
  72. 		}
  73. 	}
  74.  
  75. 	if(flag)
  76. 		cout << "Yes\n";
  77. 	else
  78. 		cout << "No\n";
  79. }
  80.  
  81. int32_t main()
  82. {
  83. #ifndef ONLINE_JUDGE
  84. 	freopen("input.txt", "r", stdin);
  85. 	freopen("output.txt", "w", stdout);
  86. #endif
  87.  
  88. 	ios_base::sync_with_stdio(false);
  89. 	cin.tie(NULL);
  90.  
  91. 	int t;
  92. 	cin>>t;
  93. 	while(t--)
  94. 		solve();
  95.  
  96. 	return 0;
  97. }
Success #stdin #stdout 0.02s 34880KB
comments (?)
stdin
copy 
2
3 2 2
1 2
2 3
1 2
2 0
4 5 2
1 4
1 2
1 3
4 2
3 4
2 1
3 0
stdout
copy 
No
Yes
https://ideone.com/hnGtXy
problem AKBAR, based on SPOJ submission 26337804 (CPP14), 2020-07-27 13:39:57
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!