daily pastebin goal
54%
SHARE
TWEET

Untitled

a guest Mar 23rd, 2019 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define BOOST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  5.  
  6. const int N = 2e5+7;
  7. const int M = 1<<19;
  8. const int logN = 20;
  9.  
  10. int segTree[M];
  11.  
  12. void addTree(int v, int value)
  13. {
  14.     v+=M;
  15.     segTree[v] += value;
  16.     while(v > 1)
  17.     {
  18.         segTree[v/2] += segTree[v];
  19.         v/=2;
  20.     }
  21. }
  22.  
  23. int getSum(int a, int b)
  24. {
  25.     a += M;
  26.     b += M;
  27.  
  28.     int res = segTree[a];
  29.     if(a != b)
  30.         res += segTree[b];
  31.  
  32.     while( a/2 != b/2)
  33.     {
  34.         if(a%2 == 0)
  35.             res += segTree[a+1];
  36.         if(b%2 == 1)
  37.             res += segTree[b-1];
  38.  
  39.         a/=2;
  40.         b/=2;
  41.     }
  42.     return res;
  43. }
  44.  
  45. vector<int> g[N];
  46. int depth[N];
  47. int lcaJumps[N][logN];
  48. int timeIn[N];
  49. int timeOut[N];
  50.  
  51. void dfsLCA(int v, int pre= -1)
  52. {
  53.     static int time = 0;
  54.  
  55.     timeIn[v] = time++;
  56.     lcaJumps[v][0] = pre;
  57.  
  58.     for(int i = 1;i < logN; ++i)
  59.     {
  60.         if(lcaJumps[v][i-1] == -1)
  61.             lcaJumps[v][i] = -1;
  62.         else
  63.             lcaJumps[v][i] = lcaJumps[lcaJumps[v][i-1]][i-1];
  64.     }
  65.  
  66.     for(auto u : g[v])
  67.     {
  68.         dfsLCA(u,v);
  69.     }
  70.  
  71.     timeOut[v] = time++;
  72. }
  73.  
  74.  
  75. //checks is v is ancestor of u
  76. bool isAncestor(int v, int u)
  77. {
  78.     if(v == -1)
  79.         return true;
  80.     if(u == -1)
  81.         return false;
  82.  
  83.     return timeIn[v] <=timeIn[u] && timeOut[v] >= timeOut[u];
  84. }
  85.  
  86. int lca(int v, int u)
  87. {
  88.     if(isAncestor(v, u))
  89.         return v;
  90.     if(isAncestor(u,v))
  91.         return u;
  92.  
  93.     for(int i = logN - 1; i >=0; --i)
  94.     {
  95.         if(!isAncestor(lcaJumps[v][i], u))
  96.             v = lcaJumps[v][i];
  97.     }
  98.     return lcaJumps[v][0]; 
  99. }
  100.  
  101. int lowestBus[N];
  102. vector<int> bussesEnds[N];
  103. int busJumps[N][logN];
  104.  
  105.  
  106. int dfsLowest(int v)
  107. {
  108.     for(auto u : g[v])
  109.     {
  110.         int res = dfsLowest(u);
  111.         if(depth[res] < depth[lowestBus[v]])
  112.             lowestBus[v] = res;
  113.     }
  114.     return lowestBus[v];
  115. }
  116.  
  117. void dfsBus(int v)
  118. {
  119.     busJumps[v][0] = lowestBus[v];
  120.  
  121.     for(int i = 1; i < logN; ++i)
  122.     {
  123.         busJumps[v][i] = busJumps[busJumps[v][i-1]][i-1];
  124.     }
  125.  
  126.     for(auto u : g[v])
  127.     {
  128.         dfsBus(u);
  129.     }
  130. }
  131.  
  132. //return vertex in tree from which we can go to u in one move
  133. //second returned value is minimal amount of busses used;
  134. pair<int,int> getPathtoNearest(int v, int u)
  135. {
  136.     int cnt = 0;
  137.  
  138.     for(int i= logN-1; i >=0; --i)
  139.     {
  140.         if(!isAncestor(busJumps[v][i], u))
  141.         {
  142.             cnt += (1<<i);
  143.             v = busJumps[v][i];
  144.         }
  145.     }
  146.  
  147.     return {v,cnt};
  148. }
  149.  
  150.  
  151. //checks if there are buses from v to u
  152. bool reachable(int v,int u)
  153. {
  154.     for(int i= logN -1 ;i >= 0; --i)
  155.     {
  156.         if(!isAncestor(busJumps[v][i], u))
  157.             v = busJumps[v][i];
  158.     }
  159.     v = busJumps[v][0];
  160.     return isAncestor(v,u);
  161. }
  162.  
  163. vector<pair<int,int>> queriesForVertex[N];
  164.  
  165. int segmentCNT[N];
  166. int result[N];
  167.  
  168. void dfsResult(int v)
  169. {
  170.     cerr<<"akt: "<<v<<' '<<g[v].size()<<'\n';
  171.     for(auto [u,id] : queriesForVertex[v])
  172.     {
  173.         segmentCNT[id] = getSum(timeIn[u], timeOut[u]);
  174.     }
  175.  
  176.     for(auto u : bussesEnds[v])
  177.     {
  178.         addTree(timeIn[u], 1);
  179.     }
  180.  
  181.  
  182.     for(auto u : g[v]
  183. )   {
  184.         cerr<<"moving from "<<v<<" to "<<u<<" size "<<g[v].size()<<'\n';
  185.         dfsResult(u);
  186.     }
  187.  
  188.     for(auto [u,id] : queriesForVertex[v])
  189.     {
  190.         if(getSum(timeIn[u], timeOut[u]) > segmentCNT[id])
  191.             --result[id];
  192.     }
  193. }
  194.  
  195. int main()
  196. {
  197.     BOOST;
  198.  
  199.     int n;
  200.     cin>>n;
  201.  
  202.     for(int i = 1;i<n; ++i)
  203.     {
  204.         int a;
  205.         cin>>a;
  206.         --a;
  207.         g[a].push_back(i);
  208.     }
  209.     dfsLCA(0);
  210.  
  211.     for(int i=0;i<n; ++i)
  212.     {
  213.         cerr<<i<<" : ";
  214.         for(auto u : g[i])
  215.             cerr<<u<<' ';
  216.         cerr<<'\n';
  217.     }
  218.  
  219.     for(int i = 0;i<n; ++i)
  220.         lowestBus[i] = i;
  221.  
  222.     cerr<<"lca done\n";
  223.     int q;
  224.     cin>>q;
  225.     for(int i= 0;i<q; ++i)
  226.     {
  227.         int u,v;
  228.         cin>>u>>v;
  229.         --u,--v;
  230.  
  231.         bussesEnds[u].push_back(v);
  232.         bussesEnds[v].push_back(u);
  233.        
  234.         int lcaUV = lca(u,v);
  235.  
  236.         if(depth[lowestBus[u]] > depth[lcaUV])
  237.             lowestBus[u] = lcaUV;
  238.  
  239.  
  240.         if(depth[lowestBus[v]] > depth[lcaUV])
  241.             lowestBus[v] = lcaUV;
  242.     }
  243.  
  244.     cerr<<"busses loaded\n";
  245.     dfsLowest(0);
  246.     dfsBus(0);
  247.  
  248.     cerr<<"queries\n";
  249.     cin>>q;
  250.     for(int i= 0;i<q; ++i)
  251.     {
  252.         int u,v;
  253.         cin>>u>>v;
  254.         --u,--v;
  255.  
  256.         int lcaUV = lca(u,v);
  257.  
  258.         if(! reachable(v, lcaUV) || ! reachable(u,lcaUV))
  259.         {
  260.             result[i] = -1;
  261.             break;
  262.         }
  263.  
  264.         int lenV, lenU;
  265.  
  266.         tie(v,lenV) = getPathtoNearest(v, lenV);
  267.         tie(u,lenU) = getPathtoNearest(u,lenU);
  268.  
  269.         result[i] = lenV +lenU;
  270.  
  271.         if(v != lcaUV && u != lcaUV)
  272.         {
  273.             queriesForVertex[v].emplace_back(u,i);
  274.         }
  275.  
  276.         if(u != lcaUV)
  277.             result[i]++;
  278.  
  279.         if(v != lcaUV)
  280.             result[i]++;
  281.     }
  282.     cerr<<"res dfs\n";
  283.     dfsResult(0);  
  284.     cerr<<"end dfs\n";
  285.     for(int i= 0;i<q; ++i)
  286.         cout<<result[i]<<'\n';
  287.  
  288. }
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