fork download
copy 
  1. #include <unordered_set>
  2. #include <unordered_map>
  3. #include <bits/stdc++.h>
  4.  
  5.  
  6. #define lli long long int
  7. #define all(x) x.begin(),x.end()
  8. #define b(x) x.begin()
  9. #define e(x) x.end()
  10. #define sz(x) x.size()
  11. #define vi vector<int>
  12. #define vli vector<long long int>
  13. #define pi pair<int,int>
  14. #define pli pair<long long int,long long int>
  15. #define pr pair
  16. #define ff first
  17. #define ss second
  18. #define vt vector
  19. #define um unordered_map
  20. #define us unordered_set
  21. #define mod 1000000007
  22. #define pb push_back
  23. #define pf push_front
  24. #define endl '\n'
  25. #define loop(i,a,b) for(lli i=a;i<b;i++)
  26. #define loopr(i,a,b) for(lli i=a;i>=b;i--)
  27. #define foit(it,x)   for(auto &it:x)
  28.  
  29. using namespace std;
  30.  
  31. int dx[] = {-1,1,0,0,-1,-1,1,1};
  32. int dy[] = {0,0,1,-1,-1,1,-1,1};
  33.  
  34. const int block = 500;
  35. static int timer = 0;
  36.  
  37. typedef struct
  38. {
  39.     int l,r,id,c,type,LCA;
  40. }query;
  41.  
  42. bool cmp(query a, query b)
  43. {
  44.     if(a.l/block!=b.l/block)
  45.     return (a.l<b.l);
  46.     return (a.r<b.r);
  47. }
  48.  
  49.  
  50. void add(int node, int freq[], int colour[], int colourPresent[])
  51. {
  52.     freq[node]++;
  53.     int col = colour[node];
  54.     if(freq[node]==1) colourPresent[col]=1;
  55.     if(freq[node]==2) colourPresent[col]=0;
  56. }
  57.  
  58. void remove(int node, int freq[], int colour[], int colourPresent[])
  59. {
  60.     freq[node]--;
  61.     int col = colour[node];
  62.     if(freq[node]==1) colourPresent[col]=1;
  63.     if(freq[node]==0) colourPresent[col] = 0;
  64. }
  65.  
  66. void dfs(int node, int par, vi adj[], int in[], int out[], int ett[], int parent[][20], int level[])
  67. {
  68.     parent[node][0]=par;
  69.     in[node]=timer;
  70.     ett[timer++]=node;
  71.     for(int &child:adj[node])
  72.     {
  73.         if(child!=par)
  74.         {
  75.             level[child]=level[node]+1;
  76.             dfs(child,node,adj,in,out,ett,parent,level);
  77.         }
  78.     }
  79.     out[node]=timer;
  80.     ett[timer++]=node;
  81. }
  82.  
  83. int lca(int a, int b, int level[], int par[][20])
  84. {
  85.     if(level[b]>level[a]) swap(a,b);
  86.     int d = level[a]-level[b];
  87.     for(int i=0;i<20;i++)
  88.     {
  89.         if(d&(1<<i)) a = par[a][i];
  90.     }
  91.  
  92.     if(a==b) return a;
  93.     for(int i=19;i>=0;i--)
  94.     {
  95.         if((par[a][i]!=-1) && (par[a][i]!=par[b][i]))
  96.         {
  97.             a = par[a][i];
  98.             b = par[b][i];
  99.         }
  100.     }
  101.     return par[a][0];
  102. }
  103.  
  104. void solve()
  105. {
  106.     int t=1;
  107.     //cin>>t;
  108.     int n;
  109.     while(scanf("%d",&n)!=EOF)
  110.     {
  111.         int q; scanf("%d",&q);
  112.         int colour[n];
  113.         for(int i=0;i<n;i++) scanf("%d",&colour[i]);
  114.         vi adj[n];
  115.         for(int i=1;i<n;i++)
  116.         {
  117.             int a,b; scanf("%d %d",&a,&b); a--,b--;
  118.             adj[a].pb(b),adj[b].pb(a);
  119.         }
  120.         int in[n],out[n],ett[2*n], level[n];
  121.         memset(level,0,sizeof level);
  122.         int parent[n][20];
  123.         memset(parent,-1,sizeof parent);
  124.         timer = 0;
  125.         dfs(0,-1,adj,in,out,ett,parent,level);
  126.  
  127.         for(int i=0;i<n;i++)
  128.         for(int j=1;j<20;j++)
  129.         {
  130.             if(parent[i][j-1]!=-1)
  131.             {
  132.                 parent[i][j] = parent[parent[i][j-1]][j-1];
  133.             }
  134.         }
  135.         query Q[q];
  136.         for(int i=0;i<q;i++)
  137.         {
  138.             int a,b,c; scanf("%d %d %d",&a,&b,&c); a--,b--;
  139.             if(in[a]>in[b]) swap(a,b);
  140.             int LCA = lca(a,b,level,parent);
  141.             if(LCA==a) Q[i]={in[a],in[b],i,c,0,LCA};
  142.             else
  143.             Q[i]={out[a],in[b],i,c,1,LCA};
  144.         }
  145.         sort(Q,Q+q,cmp);
  146.         int freq[n],colourPresent[n+10],ans[q];
  147.         memset(freq,0,sizeof freq); memset(colourPresent,0, sizeof colourPresent);
  148.         int currL = 0, currR = -1;
  149.         for(int i=0;i<q;i++)
  150.         {
  151.             while(currL>Q[i].l)
  152.             currL--,add(ett[currL],freq,colour,colourPresent);
  153.  
  154.             while(currR<Q[i].r)
  155.             currR++,add(ett[currR],freq,colour,colourPresent);
  156.  
  157.             while(currL<Q[i].l)
  158.             remove(ett[currL],freq,colour,colourPresent),currL++;
  159.  
  160.             while(currR>Q[i].r)
  161.             remove(ett[currR],freq,colour,colourPresent),currR--;
  162.  
  163.             if(Q[i].type==1) colourPresent[colour[Q[i].LCA]] = 1;
  164.             ans[Q[i].id]=colourPresent[Q[i].c];
  165.             if(Q[i].type==1) colourPresent[colour[Q[i].LCA]] = 0;
  166.         }
  167.         for(int i=0;i<q;i++)
  168.         {
  169.             if(ans[i]) printf("%s\n","Find");
  170.             else printf("%s\n","NotFind");
  171.         }
  172.         printf("%s"," ");
  173.     }
  174. }
  175.  
  176.  
  177. int main()
  178. {
  179.     clock_t start, end;
  180.     start = clock();
  181.     ios_base::sync_with_stdio(false);
  182.     cin.tie(NULL);
  183.     cout.tie(NULL);
  184.     // #ifndef ONLINE_JUDGE
  185.     // freopen("input.txt","r",stdin);
  186.     // freopen("output.txt","w",stdout);
  187.     // #endif
  188.     solve();
  189.     end = clock();
  190.     #ifndef ONLINE_JUDGE
  191.     double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
  192.     cout << "Time taken is : " << fixed
  193.          << time_taken << setprecision(5);
  194.     cout << " sec " << endl;
  195.     #endif
  196.     return 0;
  197. }
  198.  
Success #stdin #stdout 0.01s 5656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GHJSa0
problem GOT, based on SPOJ submission 28280802 (CPP14), 2021-08-04 10:12:43
language:
C++14 (gcc 8.3)
created:
2 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!