fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<stdint.h>
  4. #include<vector>
  5. #include<algorithm>
  6. #include<utility>
  7. #include<set>
  8. #include<map>
  9. #include<queue>
  10. #include<stack>
  11. #include<deque>
  12. #include<string>
  13. #include<assert.h>
  14. #include<math.h>
  15. #include<chrono>
  16. #include<random>
  17. #include<bitset>
  18.  
  19. using namespace std;
  20.  
  21. const int64_t INF = (int64_t) 1e9 + 5;
  22. const int64_t mINF = (int64_t) 2 * 1e6 + 5;
  23. const int64_t MOD = (int64_t) 1e9 + 19972207;
  24. const int nbit = 30;
  25. const int ndig = 10;
  26. const int nchar = 26;
  27. const int p1 = 31;
  28. const int p2 = 53;
  29. const int D = 4;
  30. int dr[D] = {0, 1, 0, -1};
  31. int dc[D] = {1, 0, -1, 0};
  32. // 0 right // 1 down // 2 left // 3 up
  33.  
  34. struct Solution
  35. {
  36.     int n;
  37.     int t;
  38.     int q;
  39.     int cur;
  40.     int seed;
  41.     int mul;
  42.     int add;
  43.     int LOG;
  44.     int time;
  45.     vector<int> f;
  46.     vector<int> tin;
  47.     vector<int> tout;
  48.     vector<int> pos;
  49.     vector<int> depth;
  50.     vector<vector<int> > adj;
  51.     vector<vector<int> > rmq;
  52.     vector<pair<int, int> > e;
  53.     Solution() {}
  54.  
  55.     void solve()
  56.     {
  57.         cin >> n;
  58.         t = 0;
  59.         LOG = 0;
  60.         time = 0;
  61.         adj.resize(n);
  62.         tin.resize(n);
  63.         tout.resize(n);
  64.         f.resize(n, -1);
  65.         depth.resize(n, 0);
  66.         for(int i = 0; i < n - 1; i++)
  67.         {
  68.             int u;
  69.             int v;
  70.             cin >> u >> v;
  71.             u--; v--;
  72.  
  73.             adj[u].push_back(v);
  74.             adj[v].push_back(u);
  75.             e.emplace_back(u, v);
  76.         }
  77.  
  78.         DFS();
  79.         while(MASK(LOG) <= t) LOG++;
  80.         rmq.resize(LOG, vector<int>(t, 0));
  81.         for(int i = 0; i < (int) e.size(); i++)
  82.         {
  83.             if(depth[e[i].first] < depth[e[i].second]) swap(e[i].first, e[i].second);
  84.         }
  85.  
  86.         for(int i = 0; i < t; i++)
  87.         {
  88.             rmq[0][i] = pos[i];
  89.         }
  90.  
  91.         for(int i = 1; i < LOG; i++)
  92.         {
  93.             for(int j = 0; j + MASK(i) - 1 < t; j++)
  94.             {
  95.                 int d1 = depth[ rmq[i - 1][j] ];
  96.                 int d2 = depth[ rmq[i - 1][j + MASK(i - 1)] ];
  97.  
  98.                 if(d1 < d2) rmq[i][j] = rmq[i - 1][j];
  99.                 else rmq[i][j] = rmq[i - 1][j + MASK(i - 1) ];
  100.             }
  101.         }
  102.  
  103.         cin >> q >> seed >> mul >> add;
  104.         cur = seed;
  105.         int64_t ans = 0;
  106.         for(int i = 0; i < q; i++)
  107.         {
  108.             int e1 = getRandom(n - 1);
  109.             int u1 = getRandom(n); int v1 = getRandom(n);
  110.             int e2 = getRandom(n - 1);
  111.             int u2 = getRandom(n); int v2 = getRandom(n);
  112.             int64_t tmp = e1 == e2 || u1 == v1 || u2 == v2 ? MOD - 1 : query(e1, u1, v1, e2, u2, v2);
  113.  
  114.             ans = (227LL * ans + tmp) % MOD;
  115.         }
  116.         cout << ans << "\n";
  117. //        cin >> q;
  118. //        for(int i = 0; i < q; i++)
  119. //        {
  120. //            int e1; int u1; int v1; int e2; int u2; int v2;
  121. //            cin >> e1 >> u1 >> v1 >> e2 >> u2 >> v2;
  122. //            if(e1 == e2 || u1 == v1 || u2 == v2) cout << "MOD\n";
  123. //            else cout << query(e1, u1, v1, e2, u2, v2) << "\n";
  124. //        }
  125.     }
  126.  
  127.     int query(int x, int a, int b, int y, int c, int d)
  128.     {
  129.         x--; y--; a--; b--; c--; d--;
  130.         int u1 = e[x].first; int u2 = e[y].first;
  131.         int pa = 0; int pb = 0; int pc = 0; int pd = 0;
  132.         updateP(pa, a, u1, u2); updateP(pb, b, u1, u2);
  133.         updateP(pc, c, u1, u2); updateP(pd, d, u1, u2);
  134.  
  135.         if(pa > pb)
  136.         {
  137.             swap(a, b);
  138.             swap(pa, pb);
  139.         }
  140.         if(pc > pd)
  141.         {
  142.             swap(c, d);
  143.             swap(pc, pd);
  144.         }
  145.         if(pa != pb)
  146.         {
  147.             if(pc == pd) return 1;
  148.             return (pa == pc && pb == pd);
  149.         }
  150.  
  151.         if(pa != pc) return (pa == pb) + (pc == pd);
  152.         // pa == pb && pa == pc
  153.         if(pc != pd) return 1;
  154.         // pa == pb && pa == pc && pc == pd
  155.         if(checkPaths(a, b, c, d)) return 3;
  156.         return 2;
  157.     }
  158.  
  159.     bool checkPaths(int a, int b, int c, int d)
  160.     {
  161.         int ab = LCA(a, b);
  162.         int cd = LCA(c, d);
  163.         if(Intersect(ab, a, cd, c)) return true;
  164.         if(Intersect(ab, a, cd, d)) return true;
  165.         if(Intersect(ab, b, cd, c)) return true;
  166.         if(Intersect(ab, b, cd, d)) return true;
  167.         return false;
  168.     }
  169.  
  170.     bool Intersect(int x, int y, int u, int v)
  171.     {
  172.         if(u == v || x == y) return false; // one of the path only 1 node
  173.         if(!check(x, u) && !check(u, x)) return false; // 2 different subtree
  174.  
  175.         if(check(x, u)) // x is always in the subtree of u
  176.         {
  177.             swap(x, u);
  178.             swap(y, v);
  179.         }
  180.         return (check(x, v) && x != v && LCA(y, v) != x);
  181.     }
  182.  
  183.     void updateP(int& a, int& u, int& x, int& y)
  184.     {
  185.         if(check(x, u) && check(a, x)) a = x;
  186.         if(check(y, u) && check(a, y)) a = y;
  187.     }
  188.  
  189.     bool check(int& u, int& v)
  190.     {
  191.         return tin[u] <= tin[v] && tin[v] <= tout[u];
  192.     }
  193.  
  194.     int LCA(int i, int j)
  195.     {
  196.         i = f[i]; j = f[j];
  197.         if(i > j) swap(i, j);
  198.  
  199.         int len = j - i + 1;
  200.         int k = 31 - __builtin_clz(len);
  201.         if(depth[ rmq[k][i] ] < depth[ rmq[k][j - MASK(k) + 1] ]) return rmq[k][i];
  202.         return rmq[k][j - MASK(k) + 1];
  203.     }
  204.  
  205.     void DFS(int u = 0)
  206.     {
  207.         f[u] = t++;
  208.         tin[u] = time++;
  209.         pos.push_back(u);
  210.  
  211.         for(int i = 0; i < (int) adj[u].size(); i++)
  212.         {
  213.             int v = adj[u][i];
  214.             if(f[v] != -1) continue;
  215.  
  216.             depth[v] = depth[u] + 1;
  217.             DFS(v);
  218.  
  219.             pos.push_back(u);
  220.             t++;
  221.         }
  222.         tout[u] = time++;
  223.     }
  224.  
  225.     int getRandom(int x)
  226.     {
  227.         cur = (1LL * mul * cur + add) % MOD;
  228.         return 1 + cur % x;
  229.     }
  230.  
  231.     int modsub(int t1, int t2)
  232.     {
  233.         int64_t res = t1 - t2;
  234.         if(res < 0) res += MOD;
  235.  
  236.         return res;
  237.     }
  238.  
  239.     int modadd(int t1, int t2)
  240.     {
  241.         int64_t res = t1 + t2;
  242.         if(res >= MOD) res -= MOD;
  243.  
  244.         return res;
  245.     }
  246.  
  247.     int modmul(int t1, int t2)
  248.     {
  249.         int64_t res = 1LL * t1 * t2;
  250.         return (res % MOD);
  251.     }
  252.  
  253.     bool BIT(int mask, int j)
  254.     {
  255.         return (mask & MASK(j));
  256.     }
  257.  
  258.     int MASK(int j)
  259.     {
  260.         return (1 << j);
  261.     }
  262.  
  263.     int64_t Abs(int64_t t1)
  264.     {
  265.         if(t1 < 0) return -t1;
  266.         return t1;
  267.     }
  268. };
  269.  
  270. void __startup()
  271. {
  272.     ios_base::sync_with_stdio(false);
  273.     cin.tie(NULL);
  274.  
  275.     freopen("CHUTRINH.INP", "r", stdin);
  276.     freopen("CHUTRINH.OUT", "w", stdout);
  277. }
  278.  
  279. int main()
  280. {
  281.     __startup();
  282.     int t = 1;
  283.     int sub = 0;
  284.     cin >> sub;
  285. //    cin >> t;
  286.  
  287.     for(int i = 1; i <= t; i++)
  288.     {
  289.         Solution().solve();
  290.     }
  291.  
  292.     return 0;
  293. }
  294.  
Runtime error #stdin #stdout 0.04s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/f5Y6Vs
language:
C++14 (gcc 8.3)
created:
176 days 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!