洛谷 P2147 [SDOI2008]洞穴勘测 题解【LCT】

输入输出样例

200 5
Query 123 127
Connect 123 127
Query 123 127
Destroy 127 123
Query 123 127


No
Yes
No


3 5
Connect 1 2
Connect 3 1
Query 2 3
Destroy 1 3
Query 2 3


Yes
No


说明

$latex 10\%$的数据满足$latex n≤1000, m≤20000$

$latex 20\%$的数据满足$latex n≤2000, m≤40000$

$latex 30\%$的数据满足$latex n≤3000, m≤60000$

$latex 40\%$的数据满足$latex n≤4000, m≤80000$

$latex 50\%$的数据满足$latex n≤5000, m≤100000$

$latex 60\%$的数据满足$latex n≤6000, m≤120000$

$latex 70\%$的数据满足$latex n≤7000, m≤140000$

$latex 80\%$的数据满足$latex n≤8000, m≤160000$

$latex 90\%$的数据满足$latex n≤9000, m≤180000$

$latex 100\%$的数据满足$latex n≤10000, m≤200000$

Code:

#include<cstdio>
#include<cstring>
#define ls ch[0][k]
#define rs ch[1][k]
#define which(k) (ch[1][fa[k]]==k)
#define isroot(k) (ch[0][fa[k]]!=k&&ch[1][fa[k]]!=k)
#define maxn 10100
int ch[2][maxn],fa[maxn];
int lazy[maxn];
void pushdown(int k)
{
if(lazy[k])
{
int tmp=ls;
ls=rs;
rs=tmp;
lazy[ls]^=1;
lazy[rs]^=1;
lazy[k]=0;
}
}
void Rotate(int k)
{
int y=fa[k];
if(!isroot(y))
ch[which(y)][fa[y]]=k;
bool d=which(k);
fa[k]=fa[y];
fa[y]=k;
ch[d][y]=ch[!d][k];
fa[ch[d][y]]=y;
ch[!d][k]=y;
}
int stk[10010],tp=0;
void splay(int k)
{
int x=k;
while(!isroot(x))
{
stk[++tp]=x;
x=fa[x];
}
stk[++tp]=x;
while(tp)
pushdown(stk[tp--]);

while(!isroot(k))
{
int y=fa[k];
if(!isroot(y))
Rotate(which(k)^which(y)?k:y);
Rotate(k);
}
}
void access(int k)
{
for(int x=k,y=0;x;y=x,x=fa[x])
{
splay(x);
ch[1][x]=y;
//maintain(x);
}
}
void makeroot(int k)
{
access(k);
splay(k);
lazy[k]^=1;
}
int getroot(int k)
{
access(k);
splay(k);
while(ls)
k=ls;
return k;
}
{
makeroot(x);
fa[x]=y;
}
void cut(int x,int y)
{
makeroot(x);
access(y);
splay(y);
fa[x]=ch[0][y]=0;
}
char op[100];
int main()
{
int n,m,u,v;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
scanf("%s",op);
scanf("%d%d",&u,&v);
if(op[0]=='C')
else if(op[0]=='D')
cut(u,v);
else
{
makeroot(u);
if(getroot(v)==u)
puts("Yes");
else
puts("No");
}
}
return 0;
}


2 说点什么

0 Followers

Most reacted comment
0 Comment authors
Recent comment authors
Subscribe