fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1e6+7, P=21, MOD = 1069692137, LP=7;
  5.  
  6. int pot[MAXN];
  7.  
  8. int n, q;
  9. vector<int> graf[MAXN];
  10. int kierunek[MAXN];
  11. int p[P][MAXN];
  12. int ojc[MAXN];
  13.  
  14. int pre[MAXN], rozmiar[MAXN];
  15. int hasz[MAXN];
  16. int akt_pre = 0;
  17. int dist[MAXN];
  18. int odleglosc_jedynki[MAXN];
  19.  
  20. void dfs(int v) {
  21.     akt_pre++;
  22.     pre[v] = akt_pre;
  23.     rozmiar[v] = 1;
  24.  
  25.     for(auto sasiad : graf[v]) {
  26.         dist[sasiad] = dist[v]+1;
  27.         hasz[sasiad] = (hasz[v]+pot[dist[sasiad]]*kierunek[sasiad])%MOD;
  28.         odleglosc_jedynki[sasiad] = odleglosc_jedynki[v]+1;
  29.  
  30.         if(hasz[v]==0&&kierunek[sasiad]==1) {
  31.             dist[sasiad] = 0;
  32.             hasz[sasiad] = 0;
  33.             odleglosc_jedynki[sasiad] = 0;
  34.         }
  35.  
  36.         dfs(sasiad);
  37.         rozmiar[v] += rozmiar[sasiad];
  38.     }
  39. }
  40.  
  41. bool czy_przodek(int a, int b) {
  42.     if(a==0) return 1;
  43.     return (pre[b]>=pre[a])&&(pre[b]<pre[a]+rozmiar[a]); 
  44. }
  45.  
  46. pair<int, int> lca(int a, int b) {
  47.     for(int i=P-1; i>=0; i--) {
  48.         if(hasz[p[i][a]]!=0&&hasz[p[i][b]]!=0 && hasz[p[i][a]]!=hasz[p[i][b]]) {
  49.             a = p[i][a];
  50.             b = p[i][b];
  51.         }
  52.     }
  53.     return {a, b};
  54. }
  55.  
  56. int main() {
  57.     ios_base::sync_with_stdio(0);
  58.     cin.tie(0);
  59.  
  60.  
  61.     cin >> n;
  62.  
  63.     pot[0] = 1;
  64.     for(int i=1; i<=n; i++) {
  65.         pot[i] = (pot[i-1]*LP)%MOD; 
  66.     }
  67.  
  68.     for(int i=1; i<=n; i++) {
  69.         int a, b;
  70.         cin >> a >> b;
  71.         graf[i].push_back(a);
  72.         graf[i].push_back(b);
  73.         kierunek[a] = 1;
  74.         kierunek[b] = 2;
  75.         ojc[a] = i;
  76.         ojc[b] = i;
  77.     }
  78.  
  79.     for(int i=1; i<=n; i++) {
  80.         p[0][i] = ojc[i];
  81.     }
  82.  
  83.     for(int i=1; i<P; i++) {
  84.         for(int j=1; j<=n; j++) {
  85.             p[i][j] = p[i-1][p[i-1][j]];
  86.             //cout << p[i][j] << " ";
  87.         }
  88.         //cout << "\n";
  89.     }
  90.  
  91.     dfs(1);
  92.  
  93.     /*for(int i=1; i<=n; i++) {
  94.         cout << hasz[i] << " ";
  95.     }
  96.     cout << "\n";*/
  97.  
  98.  
  99.     cin >> q;
  100.  
  101.     while(q--) {
  102.         int a, b;
  103.         cin >> a >> b;
  104.         if(hasz[a]==hasz[b]) {
  105.             cout << "TAK\n";
  106.             continue;
  107.         }
  108.  
  109.         if(odleglosc_jedynki[a]>odleglosc_jedynki[b]) {
  110.             cout << "TAK\n";
  111.             continue;
  112.         }
  113.         if(odleglosc_jedynki[b]>odleglosc_jedynki[a]) {
  114.             cout << "NIE\n";
  115.             continue;
  116.         }
  117.  
  118.         if(czy_przodek(b, a)) {
  119.             cout << "TAK\n";
  120.             continue;
  121.         }
  122.         if(czy_przodek(a, b)) {
  123.             cout << "NIE\n";
  124.             continue;
  125.         }
  126.         pair<int, int> w = lca(a, b);
  127.         //cout << w.first << " " << w.second << "\n";
  128.         if(kierunek[w.first]==2) {
  129.             cout << "TAK\n";
  130.         }
  131.         else {
  132.             cout << "NIE\n";
  133.         }
  134.     }
  135.  
  136.  
  137.  
  138.     return 0;
  139. }
Success #stdin #stdout 0.02s 79348KB
comments (?)
stdin
copy 
35
0 2
19 3
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
0 14
15 0
0 16
17 0
0 18
0 0
20 0
21 0
0 22
0 23
24 0
25 0
0 26
0 27
28 0
29 0
0 30
31 0
32 0
0 33
34 0
35 0
0 0
1
18 35
stdout
copy 
TAK
https://ideone.com/8qAQaA
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!