洛谷 2173 [ZJOI2012]网络

  1 #include<cstdio>
  2 #include<algorithm>
  3 #define N 500010
  4 #define C 20
  5 #define rg register
  6 #define ls (son[c][u][0])
  7 #define rs (son[c][u][1])
  8 using namespace std;
  9 int n,m,c,k,opt,x,y,w,top;
 10 int cnt[C][N],fa[C][N],son[C][N][2],val[N],mx[C][N],rev[C][N],st[N];
 11 inline int read(){
 12     int k=0,f=1; char c=getchar();
 13     while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
 14     while(‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
 15     return k*f;
 16 }
 17 inline bool isroot(int c,int u){
 18     return son[c][fa[c][u]][1]!=u&&son[c][fa[c][u]][0]!=u;
 19 }
 20 inline bool which(int c,int u){
 21     return son[c][fa[c][u]][1]==u;
 22 }
 23 inline void pushup(int c,int u){
 24     mx[c][u]=max(max(mx[c][ls],mx[c][rs]),val[u]);
 25 }
 26 inline void pushdown(int c,int u){
 27     rev[c][ls]^=1; rev[c][rs]^=1; rev[c][u]=0; swap(ls,rs);
 28 }
 29 void rotate(int c,int u){
 30     int f=fa[c][u],gf=fa[c][f],wh=which(c,u);
 31     if(!isroot(c,f)) son[c][gf][which(c,f)]=u;
 32     fa[c][u]=fa[c][f]; fa[c][f]=u; fa[c][son[c][u][wh^1]]=f;
 33     son[c][f][wh]=son[c][u][wh^1]; son[c][u][wh^1]=f; 
 34     pushup(c,f); pushup(c,u);
 35 }
 36 inline void splay(int c,int u){
 37     st[top=1]=u;
 38     for(rg int i=u;!isroot(c,i);i=fa[c][i]) st[++top]=fa[c][i];
 39     for(rg int i=top;i;i--) if(rev[c][st[i]]) pushdown(c,st[i]);
 40     while(!isroot(c,u)){
 41         if(!isroot(c,fa[c][u])) rotate(c,which(c,u)==which(c,fa[c][u])?fa[c][u]:u);
 42         rotate(c,u);
 43     }
 44 }
 45 inline void access(int c,int u){
 46     for(rg int s=0;u;s=u,u=fa[c][u]) splay(c,u),son[c][u][1]=s,pushup(c,u);
 47 }
 48 inline void makeroot(int c,int u){
 49     access(c,u); splay(c,u); rev[c][u]^=1;
 50 }
 51 inline int find(int c,int u){
 52     access(c,u); splay(c,u); 
 53     while(ls) u=ls; return u;
 54 }
 55 inline void split(int c,int x,int y){
 56     makeroot(c,x); access(c,y); splay(c,y);
 57 } 
 58 inline void link(int c,int x,int y){
 59     cnt[c][x]++; cnt[c][y]++;
 60     makeroot(c,x); fa[c][x]=y;
 61 }
 62 inline void cut(int c,int x,int y){
 63     split(c,x,y); int t=son[c][y][0];
 64     if(!son[c][t][1]&&t==x) 
 65         son[c][y][0]=0,fa[c][x]=0,cnt[c][x]--,cnt[c][y]--;
 66     else{
 67         while(son[c][t][1]) t=son[c][t][1];
 68         if(t==x) 
 69             son[c][fa[c][t]][0]=0,fa[c][x]=0,cnt[c][x]--,cnt[c][y]--;
 70     }
 71 }
 72 inline bool haveedge(int c,int x,int y){
 73     split(c,x,y); int t=son[c][y][0];
 74     if(!son[c][t][1]&&t==x) return 1;
 75     else{
 76         while(son[c][t][1]) t=son[c][t][1];
 77         if(t==x) return 1;
 78     }
 79     return 0;
 80 }
 81 int main(){
 82     n=read(); m=read(); c=read()-1; k=read();
 83     for(rg int i=1;i<=n;i++){
 84         val[i]=read();
 85         for(rg int j=0;j<=c;j++) mx[j][i]=val[i];
 86     }
 87     for(rg int i=1;i<=m;i++){
 88         x=read(); y=read(); w=read();
 89         link(w,x,y);
 90     }
 91     while(k--){
 92         if((opt=read())==0){
 93             x=read(),y=read();
 94             for(rg int i=0;i<=c;i++) access(i,x),splay(i,x);
 95             val[x]=y;
 96             for(rg int i=0;i<=c;i++) pushup(i,x);
 97         }
 98         if(opt==1){
 99             x=read(),y=read(),w=read(); bool linked=0; int lastcol=0;
100             for(rg int i=0;i<=c;i++)if(haveedge(i,x,y)){
101                 linked=1; lastcol=i; break;
102             }
103             if(lastcol==w&&linked){
104                 puts("Success."); continue;
105             }
106             if(!linked){
107                 puts("No such edge."); continue;
108             }
109             if(cnt[w][x]>=2||cnt[w][y]>=2){
110                 puts("Error 1."); continue;
111             }
112             if(find(w,x)==find(w,y)){
113                 puts("Error 2."); continue;
114             }
115             cut(lastcol,x,y); link(w,x,y); puts("Success.");
116         }
117         if(opt==2){
118             w=read(); x=read(); y=read();
119             if(find(w,x)!=find(w,y)){
120                 puts("-1"); continue;
121             }
122             split(w,x,y); printf("%d\n",mx[w][y]);
123         }
124     }
125 }