kananasgarli90

Parent

Sep 23rd, 2020
591
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, m, color[100001], a, b, dis[100001], fin[100001], t, root, x;
  4. vector<int>v[100001];
  5.  
  6. void dfs(int s){
  7.     color[s] = 1;
  8.     dis[s] = ++t;
  9.  
  10.     for(int i = 0; i < v[s].size(); i++){
  11.         int u = v[s][i];
  12.         if(color[u] == 0){
  13.             dfs(u);
  14.         }
  15.     }
  16.  
  17.     fin[s] = ++t;
  18. }
  19. int main()
  20. {
  21.     cin>>n;
  22.     for(int i = 1; i <= n; i++){
  23.         cin>>x;
  24.         if(x == 0){
  25.             root = i;
  26.         }
  27.         else{
  28.             v[x].push_back(i);
  29.         }
  30.     }
  31.     dfs(root);
  32.  
  33.     cin>>m;
  34.     while(m--){
  35.         cin>>a>>b;
  36.         if(dis[a] < dis[b] && fin[a] > fin[b]){
  37.             cout<<1<<endl;
  38.         }
  39.         else{
  40.             cout<<0<<endl;
  41.         }
  42.     }
  43. }
  44.  
  45.  
  46.  
RAW Paste Data