fork download
copy 
  1. // AKBAR - Akbar, the great
  2.  
  3. #include<bits/stdc++.h>
  4. #define ll long long int
  5. #define pb push_back
  6. #define vi vector<ll>
  7. #define vb vector<bool>
  8. #define vd vector<double>
  9. #define vc vector<char>
  10. #define vii vector<vi>
  11. #define mp make_pair
  12. #define vpi vector< pair<ll,ll> >
  13. #define take_input freopen("input.txt", "r", stdin)
  14. #define give_output freopen("output.txt", "w", stdout)
  15. #define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  16. #define fi first
  17. #define se second
  18. #define mod 1000000007
  19. #define min_pql priority_queue< ll, vector<ll>, greater<ll> >
  20.  
  21. using namespace std;
  22. using namespace std::chrono;
  23.  
  24.  
  25.  
  26. bool check(vii &adj, vb &vis, ll n, ll cityn, ll strn){
  27. 	queue<ll> q;
  28. 	q.push(cityn);
  29. 	if(vis[cityn]==true) return true;
  30. 	vi level(n+1, 0);
  31. 	while(!q.empty()){	
  32. 		ll k=q.front();
  33. 		q.pop();
  34. 		vis[k]=true;
  35. 		if(level[k] == strn) return false;
  36. 		for(ll i:adj[k]){
  37. 			if(!vis[i]){
  38. 				level[i] = level[k]+1;
  39. 				q.push(i);
  40. 				vis[i] = true;
  41. 			}else{
  42. 				if(level[i]>level[k]) return true;
  43. 			}
  44. 		}
  45. 	}
  46. 	return false;
  47. }
  48.  
  49.  
  50. int main(){
  51. 	fastIO;
  52. 	// take_input;
  53. 	// give_output;
  54. 	ll t;
  55. 	cin >> t;
  56. 	vi vans;
  57. 	while(t--){
  58. 		ll n,r,m;
  59. 		cin >> n >> r >> m;
  60. 		vii adj(n+1); // adjacency lists
  61. 		vpi q(m); // for storing strength and cityn
  62. 		// inserting vertices
  63. 		for(ll i=0; i<r; i++){
  64. 			ll num1, num2;
  65. 			cin >> num1 >> num2;
  66. 			adj[num1].pb(num2);
  67. 			adj[num2].pb(num1);
  68. 		}
  69. 		// inserting cityn strength
  70. 		for(auto &i:q) cin >> i.fi >> i.se;
  71. 		vb vis(n+1, false);
  72. 		vis[0]= true;
  73. 		ll flag=0;
  74. 		for(auto i:q){
  75. 			flag = check(adj, vis, n, i.fi, i.se);
  76. 			if(flag==1) break;
  77. 		}
  78. 		if(find(vis.begin(), vis.end(), false) != vis.end()) flag=1;
  79. 		if(flag==1) vans.pb(0);
  80. 		else vans.pb(1);
  81. 	}
  82. 	for(ll i:vans){
  83. 		if(i==0) cout << "NO\n";
  84. 		else cout << "YES\n";
  85. 	}
  86. }
Success #stdin #stdout 0s 4696KB
comments (?)
stdin
copy 
3
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
4 3 2
1 2
2 3
2 4
1 2
3 1
stdout
copy 
NO
YES
NO
https://ideone.com/w7KO5Y
language:
C++14 (gcc 8.3)
created:
4 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!