Advertisement
Guest User

Untitled

a guest
Feb 18th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.49 KB | None | 0 0
  1. //
  2. // main.cpp
  3. // G. Graph queries
  4. //
  5. // Created by Ahmed on 8/30/16.
  6. // Copyright © 2016 Abdellah. All rights reserved.
  7. //
  8.  
  9.  
  10. #include<set>
  11. #include<map>
  12. #include<list>
  13. #include<iomanip>
  14. #include<cmath>
  15. #include<string>
  16. #include<vector>
  17. #include<queue>
  18. #include<stack>
  19. #include<complex>
  20. #include<sstream>
  21. #include<iostream>
  22. #include<fstream>
  23. #include<algorithm>
  24. #include<numeric>
  25. #include<utility>
  26. #include<functional>
  27. #include<stdio.h>
  28. #include<assert.h>
  29. #include<memory.h>
  30. #include<bitset>
  31. #include<math.h>
  32.  
  33.  
  34.  
  35. #define f first
  36. #define s second
  37. #define pb push_back
  38. #define lp(i,a,n) for(int (i)=(a);i<=(int)(n);(i)++)
  39. #define mp make_pair
  40. #define clr(a) memset((a),0,sizeof (a))
  41. #define all(v) v.begin(),v.end()
  42. #define infll 1e15
  43.  
  44. using namespace std;
  45.  
  46. typedef long long ll;
  47. typedef pair<int, int> pii;
  48. typedef pair<double,double> pdd;
  49. typedef pair<ll, ll> pll;
  50. typedef vector<int> vi;
  51. typedef set<int> si;
  52. typedef map<int, int> mii;
  53. typedef complex<double> point;
  54. typedef pair<point, point> line;
  55. typedef pair<double , point> Circle;
  56.  
  57. int n,m,q , d[5005][2];
  58. vector<vi> adjL;
  59.  
  60. void BFS( int node ){
  61. lp( i , 0 , n+3 )
  62. d[i][0] = d[i][1] = infll;
  63.  
  64. queue< pii > Q;
  65. Q.push(mp(node,0));
  66. vector<bool> vis(n+1 , false);
  67. vis[node] = true;
  68. while (!Q.empty()) {
  69. pii cur = Q.front(); Q.pop();
  70. lp(i, 0, (int)adjL[cur.f].size()-1 ){
  71. int ch = adjL[cur.f][i];
  72. if( d[ch][(cur.s+1)&1] > cur.s+1 ){
  73. d[ch][(cur.s+1)&1] = cur.s+1;
  74. Q.push(mp(ch,cur.s+1));
  75. }
  76. }
  77.  
  78. }
  79. }
  80.  
  81. int main(int argc, const char * argv[]) {
  82. ios::sync_with_stdio(0);cin.tie(0);
  83. cin>>n>>m>>q;
  84. adjL = vector<vi> (n+2);
  85. lp(i, 1, m){
  86. int a,b;
  87. cin>>a>>b;
  88. adjL[a].pb(b);
  89. adjL[b].pb(a);
  90. }
  91.  
  92. vector<vector<pair < pair<int, ll > , int > > > queries(n+2);
  93. vector<bool> ans(q);
  94.  
  95. lp(i, 0, q-1) {
  96. ll a ,b , d1;
  97. cin>>a>>b>>d1;
  98. queries[a].pb( mp( mp(b, d1) , i ) );
  99. }
  100.  
  101. lp(i, 1, n){
  102. if( (int)queries[i].size() > 0){
  103. clr(d);
  104. BFS(i);
  105. for( pair < pair<int, ll > , int > x: queries[i] ){
  106. ans[x.s] = ( d[ x.f.f ][ x.f.s&1 ] && d[ x.f.f ][ x.f.s&1 ] <= x.f.s );
  107. }
  108. }
  109. }
  110.  
  111.  
  112. for( bool res : ans )
  113. cout<<(res ? "YES\n": "NO\n");
  114. return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement