BZOJ 3651:ネットワーク通信

同[ZJOI 2012]ネットワークでは,各ポイントをCポイントに分解してLCTでメンテナンスする.
 

#include<cstdio>

#include<map>

#define P make_pair

#define N 800002

using namespace std;

int f[N],d[8002][102],son[N][2],a[N],n;bool rev[N];

map<int,int>co[N];

inline int id(int x,int c){return x+n*c;}

inline void swap(int&a,int&b){int c=a;a=b;b=c;}

inline bool isroot(int x){return !f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;}

inline void reverse(int x){swap(son[x][0],son[x][1]),rev[x]^=1;}

inline void pb(int x){if(rev[x])reverse(son[x][0]),reverse(son[x][1]),rev[x]=0;}

inline void rotate(int x){

  int y=f[x],w=(son[y][1]==x);

  son[y][w]=son[x][w^1];

  if(son[x][w^1])f[son[x][w^1]]=y;

  if(f[y]){

    int z=f[y];

    if(son[z][0]==y)son[z][0]=x;

    if(son[z][1]==y)son[z][1]=x;

  }

  f[x]=f[y];son[x][w^1]=y;f[y]=x;

}

inline void splay(int x){

  int s=1,i=x,y;a[1]=i;

  while(!isroot(i))a[++s]=i=f[i];

  while(s)pb(a[s--]);

  while(!isroot(x)){

    y=f[x];

    if(!isroot(y)){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else rotate(y);}

    rotate(x);

  }

}

inline void access(int x){for(int y=0;x;y=x,x=f[x])splay(x),son[x][1]=y;}

inline int root(int x){access(x);splay(x);while(son[x][0])x=son[x][0];return x;}

inline void makeroot(int x){access(x);splay(x);reverse(x);}

inline void link(int x,int y){makeroot(x);f[x]=y;access(x);}

inline void cutf(int x){access(x);splay(x);f[son[x][0]]=0;son[x][0]=0;}

inline void cut(int x,int y){makeroot(x);cutf(y);}

inline void change(int x,int y,int c){

  if(x>y)swap(x,y);

  int c0=co[x][y];

  if(!c0){puts("No such cable.");return;}

  c0--;

  if(c0==c){puts("Already owned.");return;}

  if(d[x][c]==2||d[y][c]==2){puts("Forbidden: monopoly.");return;}

  int x0=id(x,c0),y0=id(y,c0),x1=id(x,c),y1=id(y,c);

  if(root(x1)==root(y1)){puts("Forbidden: redundant.");return;}

  cut(x0,y0);link(x1,y1);

  d[x][c0]--,d[y][c0]--;

  d[x][c]++,d[y][c]++;

  co[x][y]=c+1;

  puts("Sold.");

}

inline void read(int&a){char ch;a=0;while(!(((ch=getchar())>='0')&&(ch<='9')));a*=10,a+=ch-'0';while(((ch=getchar())>='0')&&(ch<='9'))(a*=10)+=ch-'0';}

int m,c,k,x,y,u,v,w;

int main(){

  read(n),read(m),read(c),read(k);

  while(m--){

    read(u),read(v),read(w);w--;if(u>v)swap(u,v);

    co[u][v]=w+1;

    x=id(u,w),y=id(v,w);

    d[u][w]++,d[v][w]++;

    link(x,y);

  }

  while(k--)read(u),read(v),read(w),change(u,v,w-1);

  return 0;

}