Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // main.cpp
- // G. Graph queries
- //
- // Created by Ahmed on 8/30/16.
- // Copyright © 2016 Abdellah. All rights reserved.
- //
- #include<set>
- #include<map>
- #include<list>
- #include<iomanip>
- #include<cmath>
- #include<string>
- #include<vector>
- #include<queue>
- #include<stack>
- #include<complex>
- #include<sstream>
- #include<iostream>
- #include<fstream>
- #include<algorithm>
- #include<numeric>
- #include<utility>
- #include<functional>
- #include<stdio.h>
- #include<assert.h>
- #include<memory.h>
- #include<bitset>
- #include<math.h>
- #define f first
- #define s second
- #define pb push_back
- #define lp(i,a,n) for(int (i)=(a);i<=(int)(n);(i)++)
- #define mp make_pair
- #define clr(a) memset((a),0,sizeof (a))
- #define all(v) v.begin(),v.end()
- #define infll 1e15
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef pair<double,double> pdd;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- typedef set<int> si;
- typedef map<int, int> mii;
- typedef complex<double> point;
- typedef pair<point, point> line;
- typedef pair<double , point> Circle;
- int n,m,q , d[5005][2];
- vector<vi> adjL;
- void BFS( int node ){
- lp( i , 0 , n+3 )
- d[i][0] = d[i][1] = infll;
- queue< pii > Q;
- Q.push(mp(node,0));
- vector<bool> vis(n+1 , false);
- vis[node] = true;
- while (!Q.empty()) {
- pii cur = Q.front(); Q.pop();
- lp(i, 0, (int)adjL[cur.f].size()-1 ){
- int ch = adjL[cur.f][i];
- if( d[ch][(cur.s+1)&1] > cur.s+1 ){
- d[ch][(cur.s+1)&1] = cur.s+1;
- Q.push(mp(ch,cur.s+1));
- }
- }
- }
- }
- int main(int argc, const char * argv[]) {
- ios::sync_with_stdio(0);cin.tie(0);
- cin>>n>>m>>q;
- adjL = vector<vi> (n+2);
- lp(i, 1, m){
- int a,b;
- cin>>a>>b;
- adjL[a].pb(b);
- adjL[b].pb(a);
- }
- vector<vector<pair < pair<int, ll > , int > > > queries(n+2);
- vector<bool> ans(q);
- lp(i, 0, q-1) {
- ll a ,b , d1;
- cin>>a>>b>>d1;
- queries[a].pb( mp( mp(b, d1) , i ) );
- }
- lp(i, 1, n){
- if( (int)queries[i].size() > 0){
- clr(d);
- BFS(i);
- for( pair < pair<int, ll > , int > x: queries[i] ){
- ans[x.s] = ( d[ x.f.f ][ x.f.s&1 ] && d[ x.f.f ][ x.f.s&1 ] <= x.f.s );
- }
- }
- }
- for( bool res : ans )
- cout<<(res ? "YES\n": "NO\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement