fork(2) download
copy 
  1. /*=================================*\
  2. |                                   |
  3. |      Md. Shahidul Islam           |
  4. |         CSE, BRUR                 |
  5. |      Rangpur, Bangladesh          |
  6. | mail: shahidul.cse.brur@gmail.com |
  7. | FB  : fb.com/shahidul.brur        |
  8. | Blog: shahidul-brur.blogspot.com  |
  9. \*=================================*/
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12.  
  13. #define ll       long long
  14. #define ull      unsinged long long
  15. #define vi       vector<int>
  16. #define vll      vector<ll>
  17. #define pii      pair<int, int>
  18. #define vii      vector<pair<int, int> >
  19. #define vs       vector<string>
  20.  
  21. #define pb              push_back
  22. #define mp              make_pair
  23. #define ff              first
  24. #define ss              second
  25. #define sz              size()
  26. #define all(a)          a.begin(), a.end()
  27. #define F(i, a, b)      for(int i=a;i<=b;i++)
  28. #define rep(i, k)       for(int i=0;i<k;i++)
  29. #define rep1(i, k)      for(int i=1;i<=k;i++)
  30. #define FORR(i, b, a)   for(int i=b;i>=a;i--)
  31. #define FOR(i, a, b)    for(int i=a;i<=b;i++)
  32. #define pi              acos(-1.0)
  33. #define eps             1e-6
  34. #define mem(a, b)       memset(a, b, sizeof(a))
  35. #define mod             1000000007
  36. #define N               10005
  37. #define inf             1e9
  38. #define LN              14
  39. vii tree[N];
  40. vi edgeCost[N];
  41. int chainHead[N], chainIndex[N], par[N][LN+5], depth[N], subSize[N], arrPos[N];
  42. int endNode[N], chainNo, pos;
  43. int costArr[N], segTree[N*4];
  44.  
  45. void initialize(int n)
  46. {
  47.     for(int i=0;i<=n;i++)
  48.     {
  49.         tree[i].clear();
  50.         edgeCost[i].clear();
  51.         chainHead[i] = -1;
  52.         for(int j=0;j<LN;j++)
  53.         {
  54.             par[i][j] = -1;
  55.         }
  56.     }
  57. }
  58. void dfs(int node, int parent, int d)
  59. {
  60.     depth[node] = d;
  61.     subSize[node] = 1;
  62.     par[node][0] = parent;
  63.     int siz = tree[node].sz;
  64.     for(int i=0;i<siz;i++)
  65.     {
  66.         int next = tree[node][i].ff;
  67.         int ind = tree[node][i].ss;
  68.         if(next!=parent)
  69.         {
  70.             endNode[ind] = next;
  71.             dfs(next, node, d+1);
  72.             subSize[node]+=subSize[next];
  73.         }
  74.     }
  75. }
  76. void initLCA(int n)
  77. {
  78.     for(int i=1;i<=n;i++)
  79.     {
  80.         for(int j=1;j<LN;j++)
  81.         {
  82.             int pre = par[i][j-1];
  83.             if(pre!=-1)
  84.                 par[i][j] = par[pre][j-1];
  85.         }
  86.     }
  87. }
  88. void HLD(int node, int cost, int parent)
  89. {
  90.     if(chainHead[chainNo]==-1)
  91.         chainHead[chainNo] = node;
  92.  
  93.     pos++;
  94.     chainIndex[node] = chainNo;
  95.     costArr[pos] = cost;
  96.     arrPos[node] = pos;
  97.  
  98.     int siz = tree[node].sz;
  99.     int heavyNode = -1;
  100.     int heavyCost = 0;
  101.  
  102.     for(int i=0;i<siz;i++)
  103.     {
  104.         int next = tree[node][i].ff;
  105.         if(next==parent)
  106.             continue;
  107.         if(heavyNode==-1 || subSize[next]>subSize[heavyNode])
  108.         {
  109.             heavyNode = next;
  110.             heavyCost = edgeCost[node][i];
  111.         }
  112.     }
  113.  
  114.     if(heavyNode!=-1)
  115.         HLD(heavyNode, heavyCost, node);
  116.  
  117.     for(int i=0;i<siz;i++)
  118.     {
  119.         int next = tree[node][i].ff;
  120.         if(next!=parent && next!=heavyNode)
  121.         {
  122.             chainNo++;
  123.             HLD(next, edgeCost[node][i], node);
  124.         }
  125.     }
  126. }
  127. void buildSegTree(int node, int b, int e)
  128. {
  129.     if(b==e)
  130.     {
  131.         segTree[node] = costArr[b];
  132.         return;
  133.     }
  134.     int mid = (b+e)>>1;
  135.     int l = node<<1;
  136.     int r = l+1;
  137.     buildSegTree(l, b, mid);
  138.     buildSegTree(r, mid+1, e);
  139.     segTree[node] = max(segTree[l], segTree[r]);
  140. }
  141. int querySegTree(int node, int b, int e, int l, int r)
  142. {
  143.     if(l>e || r<b)
  144.         return 0;
  145.     if(b>=l && e<=r)
  146.         return segTree[node];
  147.     int mid = (b+e)>>1;
  148.     int left = node<<1;
  149.     int right = left+1;
  150.     int q1 = querySegTree(left, b, mid, l, r);
  151.     int q2 = querySegTree(right, mid+1, e, l, r);
  152.     return max(q1, q2);
  153. }
  154. void updateSegTree(int node, int b, int e, int p, int val)
  155. {
  156.     if(b==e)
  157.     {
  158.         segTree[node] = val;
  159.         return;
  160.     }
  161.     int mid = (b+e)>>1;
  162.     int l = node<<1;
  163.     int r = l+1;
  164.     if(p<=mid)
  165.         updateSegTree(l, b, mid, p, val);
  166.     else updateSegTree(r, mid+1, e, p, val);
  167.     segTree[node] = max(segTree[l], segTree[r]);
  168. }
  169. int LCA(int u, int v)
  170. {
  171.     if(depth[u]<depth[v])
  172.         swap(u, v);
  173.     for(int i = LN-1;i>=0;i--)
  174.     {
  175.         if(depth[u] - (1<<i)>=depth[v])
  176.             u = par[u][i];
  177.     }
  178.  
  179.     if(u==v)
  180.         return u;
  181.     for(int i = LN-1;i>=0;i--)
  182.     {
  183.         if(par[u][i]!=-1 && par[u][i]!=par[v][i])
  184.         {
  185.             u = par[u][i];
  186.             v = par[v][i];
  187.         }
  188.     }
  189.     return par[u][0];
  190. }
  191. int queryUp(int u, int v)
  192. {
  193.     if(u==v)
  194.         return 0;
  195.     int lchain, rchain = chainIndex[v];
  196.     int ans = -1;
  197.     while(1)
  198.     {
  199.         lchain = chainIndex[u];
  200.         if(lchain==rchain)
  201.         {
  202.             if(u==v)
  203.                 break;
  204.             int cur = querySegTree(1, 1, pos, arrPos[v]+1, arrPos[u]);
  205.             ans = max(cur, ans);
  206.             break;
  207.         }
  208.         int cur = querySegTree(1, 1, pos, arrPos[chainHead[lchain]], arrPos[u]);
  209.         ans = max(ans, cur);
  210.         u = chainHead[lchain];
  211.         u = par[u][0];
  212.     }
  213.     return ans;
  214. }
  215. int queryPath(int u, int v)
  216. {
  217.  
  218.     int lca = LCA(u, v);
  219.  
  220.     int a = queryUp(u, lca);
  221.     int b = queryUp(v, lca);
  222.     return max(a, b);
  223. }
  224. void update(int idx, int val)
  225. {
  226.     int node = endNode[idx];
  227.     updateSegTree(1, 1, pos, arrPos[node], val);
  228. }
  229. int main()
  230. {
  231.     //freopen("in.txt", "r", stdin);
  232.     //freopen("out.txt", "w", stdout);
  233.     //ios_base::sync_with_stdio(false); cin.tie(NULL);
  234.     int t, n, u, v;
  235.     int cost;
  236.     scanf("%d", &t);
  237.     while(t--)
  238.     {
  239.         scanf("%d", &n);
  240.         initialize(n);
  241.         for(int i=1;i<n;i++)
  242.         {
  243.             scanf("%d %d", &u, &v);
  244.             scanf("%d", &cost);
  245.             tree[u].pb(pii(v, i));
  246.             tree[v].pb(pii(u, i));
  247.  
  248.             edgeCost[u].pb(cost);
  249.             edgeCost[v].pb(cost);
  250.         }
  251.         dfs(1, 0, 0);
  252.  
  253.         initLCA(n);
  254.  
  255.         pos = -1;
  256.         chainNo = 1;
  257.         HLD(1, 0, -1);
  258.  
  259.         buildSegTree(1, 1, pos);
  260.         char cmd[14];
  261.         scanf("%s", cmd);
  262.         while(cmd[0]!='D')
  263.         {
  264.             if(cmd[0]=='Q')
  265.             {
  266.                 scanf("%d %d", &u, &v);
  267.                 printf("%d\n", queryPath(u, v));
  268.             }
  269.             else
  270.             {
  271.                 int edge;
  272.                 int val;
  273.                 scanf("%d", &edge);
  274.                 scanf("%d", &val);
  275.                 update(edge, val);
  276.             }
  277.             scanf("%s", cmd);
  278.         }
  279.     }
  280.     return 0;
  281. }
  282.  
Success #stdin #stdout 0s 4880KB
comments (?)
stdin
copy 
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
stdout
copy 
1
3
https://ideone.com/wCmdPH
problem spoj/QTREE, verdict:TLE
language:
C++14 (clang 8.0)
created:
7 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!