Lvat_s Blog

LCT

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;

int n,m,c,t,have[10005][105];
map<int,int> Mp[1000005];

struct Node{
int rev;
Node *ch[2],*fa;
Node(Node *fat);
void Pushdown();
}*root[1000005],*Null;

Node::Node(Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
rev=0;
}

Node *GetNull(){
Node *re=new Node(re);
re->rev=0;
re->ch[0]=re->fa=re->ch[1]=re;
return re;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0],ch[1]);
	rev=0;
}
}

int Notroot(Node *x){
return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);
}

void Prepare(Node *x){
if(Notroot(x))Prepare(x->fa);
x->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
}

void Link(Node *u,Node *v){
Makeroot(u);
u->fa=v;
}

void Cut(Node *u,Node *v){
Makeroot(u);
Access(v);
Splay(v);
if(v->ch[0]==u){v->ch[0]=Null;u->fa=Null;}
}

Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}

int GetPoint(int x,int y){
return x+(y-1)*n;
}

Node *ToLct(int x,int c){
return root[GetPoint(x,c)];
}

void Change(int x,int y,int z){
int Tok=Mp[x][y];
if(Tok==0){puts("No such cable.");return;}
if(Tok==z){puts("Already owned.");return;}
//printf("%d %d\n",have[x][z],have[y][z]);
if(have[x][z]==2 || have[y][z]==2){puts("Forbidden: monopoly.");return;}
Node *u1=ToLct(x,Tok),*u2=ToLct(x,z),*v1=ToLct(y,Tok),*v2=ToLct(y,z);
//printf("%d %d\n",Find(u2),Find(v2));
if(Find(u2)==Find(v2)){puts("Forbidden: redundant.");return;}
Cut(u1,v1);
have[x][Tok]--;
have[y][Tok]--;
have[x][z]++;
have[y][z]++;
Mp[x][y]=z;
Link(u2,v2);
puts("Sold.");
}

int main(){
freopen("3651.in","r",stdin);
freopen("3651.out","w",stdout);
scanf("%d %d %d %d",&n,&m,&c,&t);
Null=GetNull();
for(int i=1;i<=n*c;i++){root[i]=new Node(Null);}
//printf("%d %d %d %d\n",Null,Null->ch[0],Null->ch[1],Null->fa);
for(int i=1;i<=m;i++){
	int s1,s2,k;
	scanf("%d %d %d",&s1,&s2,&k);
	if(s1>s2)swap(s1,s2);
	have[s1][k]++;
	have[s2][k]++;
	Mp[s1][s2]=k;
	//printf("%d %d %d | %d %d N*C:%d\n",s1,s2,k,GetPoint(s1,k),GetPoint(s2,k),n*c);
	Node *x=ToLct(s1,k),*y=ToLct(s2,k);
	Link(x,y);
}
for(int i=1;i<=t;i++){
	int s1,s2,k;
	scanf("%d %d %d",&s1,&s2,&k);
	if(s1>s2)swap(s1,s2);
    Change(s1,s2,k);
}
return 0;
}