fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define    f               first
  5. #define    s               second
  6. #define    pb              push_back
  7. #define    mp              make_pair
  8. #define    sz              10100
  9.  
  10. int n;
  11. vector<int> adj[sz+5],vden1[sz+5],vden2[sz+5],costn[sz+5];
  12. int anc[sz+5][15];
  13. int parent[sz+5],subtree[sz+5];
  14. int mainarr[sz+5];
  15. int vchain[sz+5],povinc[sz+5];
  16. int headofchain[sz+5];
  17. int level[sz+5];
  18. int tree[6*sz +5];
  19.  
  20. int m=0,chaino=0,den=0;
  21. int z=0;
  22. void build(int node,int s,int e) {
  23.     z++;
  24.     if(s==e) {
  25.         tree[node]=mainarr[s];
  26.     }
  27.     else {
  28.  
  29.         int mid=(s+e)/2;
  30.         build(2*node,s,mid);
  31.         build(2*node +1,mid+1,e);
  32.         tree[node]= tree[2*node]>tree[2*node +1] ? tree[2*node] : tree[2*node +1];
  33.     }
  34. }
  35.  
  36. void update(int node,int s,int e,int idx,int val) {
  37.     z++;
  38.     if(s==e) {
  39.         tree[node]=val;
  40.         mainarr[idx]=val;
  41.     }
  42.     else {
  43.  
  44.         int mid=(s+e)/2;
  45.  
  46.         if(s<=idx && idx<=mid) {
  47.             update(2*node,s,mid,idx,val);
  48.         }
  49.         else {
  50.             update(2*node +1,mid+1,e,idx,val);
  51.         }
  52.         tree[node]= tree[2*node]>tree[2*node +1] ? tree[2*node] : tree[2*node +1];
  53.     }
  54. }
  55.  
  56. int query(int node,int s,int e,int l,int r) {
  57.     z++;
  58.     if(r<s || e<l) return -1;
  59.  
  60.     if(s>=l  && e<=r) return tree[node];
  61.  
  62.     int mid=(s+e)/2;
  63.  
  64.     int p1=query(2*node,s,mid,l,r);
  65.     int p2=query(2*node +1,mid+1,e,l,r);
  66.  
  67.     return p1>p2 ? p1 : p2;
  68. }
  69.  
  70.  
  71. void dfs1(int cur,int prev) {
  72.     z++;
  73.     int i,j,k;
  74.     anc[cur][0]=prev;
  75.     subtree[cur]=1;
  76.     parent[cur]=prev;
  77.  
  78.     for(i=0;i<adj[cur].size();i++) {
  79.         z++;
  80.         if(adj[cur][i]!=prev) {
  81.  
  82.             level[adj[cur][i]]=level[cur] +1;
  83.             dfs1(adj[cur][i],cur);
  84.  
  85.             subtree[cur]+=subtree[adj[cur][i]];
  86.         }
  87.     }
  88. }
  89.  
  90. void hld1(int cur,int prev,int cost) {
  91.     z++;
  92.     int i,j;
  93.  
  94.     if(den==0) {
  95.         headofchain[chaino]=cur;
  96.         den=1;
  97.     }
  98.     vchain[cur]=chaino;
  99.     povinc[cur]=m;
  100.     mainarr[m++]=cost;
  101.  
  102.     int mss=-1,vtx,ec;
  103.  
  104.     for(i=0;i<adj[cur].size();i++) {
  105.         z++;
  106.         if(adj[cur][i]!=prev) {
  107.  
  108.             if(subtree[adj[cur][i]]>mss || mss==-1) {
  109.  
  110.                 mss=subtree[adj[cur][i]];
  111.                 vtx=adj[cur][i];
  112.                 ec=costn[cur][i];
  113.             }
  114.         }
  115.     }
  116.  
  117.     if(mss!=-1) hld1(vtx,cur,ec);
  118.  
  119.     for(i=0;i<adj[cur].size();i++) {
  120.         z++;
  121.         if(adj[cur][i]!=prev && adj[cur][i]!=vtx) {
  122.             den=0;
  123.             chaino++;
  124.             hld1(adj[cur][i],cur,costn[cur][i]);
  125.         }
  126.     }
  127. }
  128.  
  129. void precompute() {
  130.  
  131.     int i,j;
  132.     for(i=1;i<=n;i++) {
  133.         for(j=1;j<14;j++) {
  134.             if(anc[i][j-1]!=-1) {
  135.                 z++;
  136.                 anc[i][j]=anc[anc[i][j-1]][j-1];
  137.             }
  138.         }
  139.     }
  140. }
  141.  
  142. int lca(int x,int y) {
  143.     z++;
  144.     int i,j,k,lg;
  145.     if(level[y]>level[x]) {
  146.         int swap=x;
  147.         x=y;
  148.         y=swap;
  149.     }
  150.  
  151.     int diff=level[x]-level[y];
  152.     for(int i=0;i<14;i++) if((diff>>i)&1) x=anc[x][i];
  153.     if(x==y) return x;
  154.  
  155.     for(i=13;i>=0;i--) {
  156.         z++;
  157.         if(anc[x][i]!=-1 && anc[x][i]!=anc[y][i]) {
  158.             x=anc[x][i];
  159.             y=anc[y][i];
  160.             //return parent[x];
  161.         }
  162.     }
  163.     return parent[x];
  164. }
  165.  
  166. int querybreak(int u,int v) {
  167.  
  168.     z++;
  169.     //if(level[v]>level[u]) swap(u,v); // level of u will always be greater than v
  170.  
  171.     int uchain=vchain[u];
  172.     int vchaino=vchain[v];
  173.     int ans=0,val,mne,mxe;
  174.     while(1) {
  175.  
  176.         if(u==v) break;
  177.         z++;
  178.         uchain=vchain[u];
  179.         //cout<<"uchain="<<uchain<<" "<<vchaino<<"\n";
  180.         if(uchain==vchaino) {  // u at higher level and v at lower level
  181.  
  182.             //  if(level[v]>level[u]) {
  183.             //      int swap=u;
  184.             //      u=v;
  185.             //      v=swap;
  186.             //  }
  187.              if(povinc[v]+1 > povinc[u])
  188.              {
  189.              	mne=povinc[u];
  190.              	mxe=povinc[v]+1;
  191.              }
  192.              else
  193.              {
  194.              	mxe=povinc[u];
  195.              	mne=povinc[v]+1;
  196.              }
  197.              //cout<<"mne="<<mne<<" mxe="<<mxe<<"\n";
  198.              val=query(1,1,m,mne,mxe);
  199.              if(val > ans)
  200.              ans=val;
  201.              break;
  202.         }
  203.  
  204.         //cout<<povinc[u]<<" "<<headofchain[uchain]<<" "<<povinc[headofchain[uchain]]<<"\n";
  205.         if(povinc[u] > povinc[headofchain[uchain]])
  206.         {
  207.         	mne=povinc[headofchain[uchain]];
  208.             mxe=povinc[u];
  209.         }
  210.         else
  211.         {
  212.         	mxe=povinc[headofchain[uchain]];
  213.             mne=povinc[u];
  214.         }
  215.  
  216.         val=query(1,1,m,mne,mxe);
  217.         //ans=maxi(ans,val);
  218.         if(val > ans)
  219.         ans=val;
  220.         u=headofchain[uchain];
  221.         u=parent[u];
  222.     }
  223.     return ans;
  224. }
  225.  
  226. int _querybreak(int u,int v) {
  227.  
  228.     z++;
  229.     int la=lca(u,v);
  230.     // if(level[v]>level[u]) {
  231.     //     int swap=u;
  232.     //     u=v;
  233.     //     v=swap;
  234.     // }
  235.  
  236.     // cout<<"u="<<u<<" v="<<v<<"\n";
  237.     // cout<<"lca="<<la<<"\n";
  238.  
  239.     int v1=querybreak(u,la);
  240.     //cout<<"\n";
  241.     int v2=querybreak(v,la);
  242.  
  243.     //cout<<"v1="<<v1<<" v2="<<v2<<"\n";
  244.     //return maxi(v1,v2);
  245.     return v1>v2 ? v1 : v2;
  246. }
  247.  
  248. int main() {
  249.  
  250.     // ios_base::sync_with_stdio(0);
  251.     // cin.tie(0);
  252.     // cout.tie(0);
  253.  
  254.     int i,j,k;
  255.  
  256.     int t;
  257.     scanf("%d",&t);
  258.  
  259.     clock_t start=clock();
  260.     while(t--) {
  261.  
  262.         scanf("%d",&n);
  263.  
  264.         chaino=0;m=0;den=0;
  265.         for(i=0;i<=n;i++) {
  266.             z++;
  267.             adj[i].clear();
  268.             costn[i].clear();
  269.             vden1[i].clear();
  270.             vden2[i].clear();
  271.             headofchain[i]=-1;
  272.             for(j=1;j<=14;j++) {
  273.                 anc[i][j]=-1;
  274.             }
  275.         }
  276.         int u,v,ec;
  277.  
  278.         for(i=1;i<=(n-1);i++) {
  279.             z++;
  280.             scanf("%d %d %d\n",&u,&v,&ec);
  281.             adj[u].pb(v);
  282.             adj[v].pb(u);
  283.             costn[u].pb(ec);
  284.             costn[v].pb(ec);
  285.             vden1[i].pb(u);
  286.             vden2[i].pb(v);
  287.         }
  288.         level[1]=0;
  289.         dfs1(1,0);
  290.         hld1(1,0,0);
  291.         precompute();
  292.         m=m-1;
  293.         build(1,1,m);
  294.  
  295.         int x,y;
  296.        // cout<<"mainarray"<<endl;
  297.         //for(int i=1;i<=n;i++)
  298.        // {cout<<mainarr[i]<<" ";
  299.        // }
  300.        // cout<<endl;
  301.         while(1) {
  302.             z++;
  303.             char s[10];
  304.             scanf("%s",s);
  305.             if(s[0]=='D') break;
  306.  
  307.             if(s[0]=='Q') {
  308.                scanf("%d %d",&x,&y);
  309.                printf("%d\n",_querybreak(x,y));
  310.             }
  311.             else {
  312.                 scanf("%d %d",&x,&y);
  313.                 //cout<<"x="<<x<<" y="<<y<<"\n";
  314.                 int fn=vden1[x][0],sn=vden2[x][0];
  315.  
  316.                 //cout<<fn<<" "<<sn<<"\n";
  317.                 if(level[sn]>level[fn]) {
  318.  
  319.                     int swap=fn;
  320.                     fn=sn;
  321.                     sn=swap;
  322.                 }
  323.                 //cout<<povinc[fn]<<"\n";
  324.                 update(1,1,m,povinc[fn],y);
  325.                 //cout<<tree[2]<<"\n";
  326.             }
  327.         }
  328.     }
  329.     //cout<<"total_itern="<<z<<"\n";
  330.     //double dur=(clock()- start)*1.0/(CLOCKS_PER_SEC);
  331.     //cout<<fixed<<dur<<"\n";
  332.     return 0;
  333. }
Time limit exceeded #stdin #stdout 5s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/i2aO3C
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 years ago
visibility:
secret

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!