SHARE
TWEET

Untitled

warrior98 Apr 19th, 2019 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define NMAX 100005
  3. #define pb push_back
  4.  
  5. using namespace std;
  6.  
  7. int v[NMAX], fr[NMAX*10],res[2*NMAX],n,sqrt_;
  8. int LCA[18][NMAX], depth[NMAX];
  9. bool viz[NMAX];
  10. int euler[2*NMAX], nrord;
  11. int in[NMAX], out[NMAX];
  12. vector<int> G[NMAX];
  13.  
  14.  
  15. struct query {
  16.     int st, dr, i;
  17. } q[2*NMAX];
  18.  
  19. void DFS(int node, int level) {
  20.     euler[++nrord] = node;
  21.     LCA[0][nrord] = node;
  22.     in[node] = nrord;
  23.  
  24.     depth[node] = level;
  25.     viz[node] = 1;
  26.  
  27.     for(auto it:G[node])
  28.         if(!viz[it])
  29.             DFS(it, level+1);
  30.  
  31.     euler[++nrord] = node;
  32.     out[node] = nrord;
  33. }
  34.  
  35. bool mo(query A, query B) {
  36.     if(A.st/sqrt_ == B.st/sqrt_)
  37.         return A.dr < B.dr;
  38.     return A.st/sqrt_ < B.st/sqrt_;
  39. }
  40.  
  41. void remove(int pos, int &ans) {
  42.     --fr[v[pos]];
  43.     if(fr[v[pos]] == 0) --ans;
  44. }
  45.  
  46. void insert(int pos, int &ans) {
  47.     ++fr[v[pos]];
  48.     if(fr[v[pos]] == 1) ++ans;
  49. }
  50.  
  51. int getLCA(int x, int y) {
  52.     if(depth[x] > depth[y]) swap(x,y);
  53.  
  54.  
  55. }
  56.  
  57. int main() {
  58.     int m,i,x,y;
  59.  
  60.     freopen("fisier.in", "r", stdin);
  61.  
  62.     cin>>n>>m;
  63.     map<int,int> normalized;
  64.     for(i=1;i<=n;++i) {
  65.         cin >> v[i];
  66.  
  67.         if(normalized.find(v[i]) == normalized.end())
  68.             normalized[v[i]] = normalized.size();
  69.  
  70.         v[i] = normalized[v[i]];
  71.     }
  72.  
  73.     for(i=1;i<n;++i) {
  74.         cin>>x>>y;
  75.         G[x].pb(y);
  76.         G[y].pb(x);
  77.     }
  78.  
  79.     DFS(1,0);
  80.     for(i=1;i<=n;++i) {
  81.         cout << in[i] << ' ' << out[i] << '\n';
  82.     }
  83.  
  84.     // LCA
  85.     for(i=1;(1<<i)<=nrord;++i) {
  86.         for(j=1;j+(1<<i)-1<=nrord;++j) {
  87.             if(depth[LCA[i-1][j]] < depth[LCA[i-1][j+(1<<i)]])
  88.                 LCA[i][j] = LCA[i-1][j];
  89.             else LCA[i][j] = LCA[i-1][j+(1<<i)];
  90.         }
  91.     }
  92.  
  93.     // for(i=1;i<=m;++i) {
  94.     //     cin >> q[i].st >> s[i].dr;
  95.     //     q[i].i = i;
  96.     //
  97.     //     getLCA(q[i].st, q[i].dr);
  98.     // }
  99.  
  100.     return 0;
  101. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top