fork download 
  1. /*
  2. ID: varunra2
  3. LANG: C++
  4. TASK: milkvisits
  5. */
  6. // test case failing: 
  7. //29945 81162 5
  8. //line number 100144
  9.  
  10. #include<bits/stdc++.h>
  11.  
  12. using namespace std;
  13.  
  14. #ifdef DEBUG
  15. #include <debug.h>
  16. #endif
  17.  
  18. #define EPS 1e-9
  19. #define IN(A, B, C) assert(B <= A && A <= C)
  20. #define INF (int)1e9
  21. #define MEM(a, b) memset(a, (b), sizeof(a))
  22. #define MOD 1000000007
  23. #define MP make_pair
  24. #define PB push_back
  25. #define all(cont) cont.begin(), cont.end()
  26. #define rall(cont) cont.end(), cont.begin()
  27. #define x first
  28. #define y second
  29.  
  30. const double PI = acos(-1.0);
  31. typedef long long ll;
  32. typedef long double ld;
  33. typedef pair<int, int> PII;
  34. typedef map<int, int> MPII;
  35. typedef multiset<int> MSETI;
  36. typedef set<int> SETI;
  37. typedef set<string> SETS;
  38. typedef vector<int> VI;
  39. typedef vector<PII> VII;
  40. typedef vector<VI> VVI;
  41. typedef vector<string> VS;
  42.  
  43. #define rep(i, a, b) for(int i = a; i < (b); ++i)
  44. #define trav(a, x) for(auto& a : x)
  45. #define sz(x) (int)(x).size()
  46. typedef pair<int, int> pii;
  47. typedef vector<int> vi;
  48.  
  49. #ifdef DEBUG
  50. #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  51. #else
  52. #define debug(...) 42
  53. #endif
  54.  
  55. // util functions
  56.  
  57. // segtree impl
  58. //qry: contains int x in range l ... r
  59.  
  60. const int MXN = 100000;
  61. int n, m;
  62.  
  63. VVI segtree(4*MXN);
  64.  
  65.  
  66. void segbuild(VI& a, int vert, int left, int right) {
  67.   if(left == right) {
  68.     segtree[vert] = VI (1, a[left]);
  69.   }
  70.   else {
  71.     int mid = left + right;
  72.     mid /= 2;
  73.     //debug (vert);
  74.     segbuild(a, 2*vert, left, mid);
  75.     segbuild(a, 2*vert + 1, mid + 1, right);
  76.     merge(segtree[2*vert].begin(), segtree[2*vert].end(), segtree[2*vert + 1].begin(),
  77.      segtree[2*vert + 1].end(), back_inserter(segtree[vert]));
  78.   }
  79. }
  80.  
  81. void segbuild(VI& a) {
  82.   segbuild(a, 1, 0, n - 1);
  83. }
  84.  
  85.  
  86. int segqry(int vert, int left, int right, int l, int r, int x) {
  87.   if(l > r) return INF;
  88.   if(right < l || left > r) return INF;
  89.  
  90.   if(left >= l && right <= r) {
  91.     auto it = lower_bound(segtree[vert].begin(), segtree[vert].end(), x);
  92.     if(it != segtree[vert].end()) return *it;
  93.     return INF;
  94.   }
  95.  
  96.  
  97.   int mid = left + right;
  98.   mid /= 2;
  99.  
  100.   int ret = min(segqry(2*vert, left, mid, l, r, x), 
  101.              segqry(2*vert + 1, mid + 1, right, l, r, x));
  102.  
  103.   //debug (vert, left, right, l, r, ret);
  104.   return ret;
  105. }
  106.  
  107. int segqry(int l, int r, int x) {
  108.   return segqry(1, 0, n - 1, l, r, x);
  109. }
  110.  
  111.  
  112. //hld impl
  113. const int MXD = 20;
  114. //lca impl w/ binary lifting
  115. VVI lca(MXN, VI(MXD, 0));
  116. VI dist(MXN);
  117.  
  118. void setLCA() {
  119.   for(int j = 1; j < MXD; j++) {
  120.     for(int i = 0; i < n; i++) {
  121.       lca[i][j] = lca[lca[i][j - 1]][j - 1];
  122.     }
  123.   }
  124. }
  125.  
  126. int getLCA(int u, int v) {
  127.   if(dist[u] < dist[v]) swap(u, v);
  128.   for(int j = MXD - 1; j >= 0; j--) {
  129.     if(dist[u] - (1 << j) >= dist[v]) {
  130.       u = lca[u][j];
  131.     }
  132.   }
  133.   for(int j = MXD - 1; j >= 0; j--) {
  134.     if(lca[u][j] != lca[v][j]) {
  135.       u = lca[u][j];
  136.       v = lca[v][j];
  137.     }
  138.   }
  139.  
  140.   if(u != v) {
  141.    return lca[u][0];
  142.   }
  143.  
  144.   return u;
  145. }
  146.  
  147. VVI adj(MXN);
  148. VI subtreesz(MXN, 0);
  149. VI vertsegtree(MXN);
  150. VI topseg(MXN);
  151. VI vals(MXN);
  152.  
  153.  
  154. void firstinit(int x) {
  155.   segtree.resize(4*x);
  156.   lca.resize(x);
  157.   adj.resize(x);
  158.   subtreesz.resize(x);
  159.   vertsegtree.resize(x);
  160.   topseg.resize(x);
  161.   vals.resize(x);
  162.   dist.resize(x);
  163. }
  164.  
  165. void dfsinits(int ind, int par) {
  166.   subtreesz[ind]++;
  167.   for(auto& x: adj[ind]) {
  168.     if(x == par) continue;
  169.     dist[x] = dist[ind] + 1;
  170.     lca[x][0] = ind;
  171.     dfsinits(x, ind);
  172.     subtreesz[ind] += subtreesz[x];
  173.   }
  174. }
  175.  
  176. void dfsmapping(int pos, int top, int par, int& curind) {
  177.   vertsegtree[pos] = curind++;
  178.   topseg[pos] = top;
  179.   int mxsiz = -1;
  180.   int mxchild = -1;
  181.   for(auto& x: adj[pos]) {
  182.     if(x == par) continue;
  183.     if(subtreesz[x] > mxsiz) {
  184.       mxsiz = subtreesz[x];
  185.       mxchild = x;
  186.     }
  187.   }
  188.   if(mxchild == -1) {
  189.     return;
  190.   }
  191.   dfsmapping(mxchild, top, pos, curind);
  192.   for(auto& x: adj[pos]) {
  193.     if(x == par) continue;
  194.     if(x == mxchild) continue;
  195.     dfsmapping(x, x, pos, curind); 
  196.   }
  197. }
  198.  
  199. void initHLD() {
  200.   dfsinits(0, -1);
  201.   setLCA();
  202.   int curind = 0;
  203.   dfsmapping(0, 0, -1, curind);
  204. }
  205.  
  206. bool pqry(int u, int v, int x) {
  207.   int ret = INF;
  208.   if(u == v) {
  209.     ret = vals[u];
  210.   }
  211.   while(u != v) {
  212.  
  213.     if(topseg[u] == u) {
  214.       if(vals[u] >= x) ret = min(ret, vals[u]); // this is light edge so we are switching to heavy
  215.     //debug("light ", u);
  216.  
  217.       u = lca[u][0]; // getting to parent
  218.     }
  219.     else if(dist[topseg[u]] > dist[v]) {
  220.       ret = min(ret, segqry(vertsegtree[topseg[u]], vertsegtree[u], x));      
  221.       u = lca[topseg[u]][0];
  222.     //debug("heavy1 ", u);
  223.     }
  224.     else {
  225.       ret = min(ret, segqry(vertsegtree[v], vertsegtree[u], x));
  226.       break;
  227.     }
  228.     debug(ret);
  229.   }
  230.   return ret == x;
  231. }
  232.  
  233. int qry(int u, int v, int x) {
  234.   int l = getLCA(u, v);
  235.   debug(l);
  236.   //debug (u, v, l);
  237.   if(pqry(u, l, x) || pqry(v, l, x)) return 1;
  238.   return 0;
  239. }
  240.  
  241.  
  242.  
  243.  
  244. int main() {
  245. #ifndef ONLINE_JUDGE
  246.   freopen("milkvisits.in", "r", stdin);    
  247.   freopen("milkvisits.out", "w", stdout); 
  248. #endif
  249.   cin.sync_with_stdio(0); cin.tie(0);
  250.  
  251.   cin >> n >> m;
  252.  
  253.   firstinit(n);
  254.  
  255.   for(int i = 0; i < n; i++) {
  256.     cin >> vals[i];
  257.   }
  258.  
  259.  
  260.   for(int i = 0; i < n - 1; i++) {
  261.     int u, v;
  262.     cin >> u >> v;
  263.     u--;
  264.     v--;
  265.     adj[u].PB(v);
  266.     adj[v].PB(u);
  267.   }
  268.  
  269.   initHLD();
  270.  
  271.   VI reorder(n);
  272.  
  273.   for(int i = 0; i < n; i++) {
  274.     reorder[vertsegtree[i]] = vals[i];
  275.   }
  276.   VI inds;
  277.   for(int i = 0; i < n; i++) {
  278.     if(vals[i] == 5) inds.PB(i);
  279.   }
  280.   debug(inds);
  281.   //debug (vals);
  282.   //debug (reorder);
  283.   debug (lca[29944]);
  284.   debug (lca[81161]);
  285.   //debug (dist);
  286.   //debug(topseg);
  287.   //debug(vertsegtree);
  288.  
  289.   segbuild(reorder);
  290.  
  291.  
  292.  
  293.   for(int i = 0; i < m; i++) {
  294.     int u, v, x;
  295.     cin >> u >> v >> x;
  296.     u--;
  297.     v--;
  298.     if (v > u) swap(u, v);
  299.     cout << qry(u, v, x);
  300.   }
  301.  
  302.   cout << endl;
  303.  
  304.  
  305.  
  306.   return 0;
  307. }
  308.  
Runtime error #stdin #stdout 0.01s 28692KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/KvugUw
language:
C++14 (gcc 8.3)
created:
4 years 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!