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