fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e7+5;
  4. vector<int> adj[N];
  5. int strength[N];
  6. bool visited[N];
  7. int parent[N];
  8. int flag = 1;
  9. void bfs(int node)
  10. {
  11. 	queue<int> q;
  12. 	q.push(node);
  13. 	parent[node] = -1;
  14. 	while(!q.empty()){
  15. 		int cur_node = q.front();
  16. 		q.pop();
  17. 		if(strength[cur_node] == 0)
  18. 			continue;
  19. 		for(auto next_node : adj[cur_node]){
  20. 			if(next_node == parent[cur_node])
  21. 				continue;
  22. 			if(!visited[next_node]){
  23. 				visited[next_node] = true;
  24. 				strength[next_node] = strength[cur_node] - 1;
  25. 				parent[next_node] = cur_node;
  26. 				q.push(next_node);
  27. 			}
  28. 			else if(strength[next_node] > strength[cur_node] - 1 && parent[cur_node] != parent[next_node]){
  29. 				flag = 0;
  30. 				return;
  31. 			}
  32. 		}	
  33. 	}
  34. }
  35. int main()
  36. {
  37. 	ios_base::sync_with_stdio(0);
  38. 	cin.tie(0);
  39. 	int t;
  40. 	cin >> t;
  41. 	while(t--){
  42. 		flag = 1;
  43. 		memset(visited,false,sizeof(visited));
  44. 		int n,r,m;
  45. 		cin >> n >> r >> m;
  46. 		for(int i = 0; i < N;i++){
  47. 			adj[i].clear();
  48. 		}
  49. 		for(int i = 0; i < r;i++){
  50. 			int u,v;
  51. 			cin >> u >> v;
  52. 			adj[u].push_back(v);
  53. 			adj[v].push_back(u);
  54. 		}
  55. 		memset(strength,-1,sizeof(strength));
  56. 		for(int i = 0; i < m;i++){
  57. 			int k,s;
  58. 			cin >> k >> s;
  59. 			if(visited[k])
  60. 				flag = 0;
  61. 			strength[k] = s;
  62. 			visited[k] = true;
  63. 			if(flag)
  64. 				bfs(k);
  65. 		}
  66. 		for(int i = 1; i <= n;i++){
  67. 			if(visited[i] == -1)
  68. 				flag = 0;
  69. 		}
  70. 		if(flag)
  71. 			puts("Yes");
  72. 		else
  73. 			puts("No");
  74. 	}
  75. }
Runtime error #stdin #stdout 0.07s 247260KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PTFVfJ
problem AKBAR, based on SPOJ submission 26297069 (CPP14), 2020-07-18 09:26:30
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!