[BZOJ2049][SDOI2008]Cave동굴탐사LCT누드문제모형문제수조판
LCT 같은 건 말 안 할 거야. 엉망진창이야. 어차피 이 편은 자용이야.
마찬가지로 이 블로그를 보는 사람들은 먼저 다른 곳에 가서 LCT를 배운 후에 나에게 와서 코드를 긁어모을 수 있다.
코드:
#include
#include
#include
#include
#define ls son[x][0]
#define rs son[x][1]
#define is(x) (x==son[fa[x]][1])
#define isroot(x) (x!=son[fa[x]][0]&&x!=son[fa[x]][1])
#define N 10010
#define inf 0x3f3f3f3f
using namespace std;
int pos[N],n,m;
char ttt[10];
struct LCT
{
int son[N][2],fa[N],cnt;
bool flag[N];
int stack[N],top;
void joint(int x,int y,int d){fa[x]=y,son[y][d]=x;}
void reverse(int x)
{
flag[x]^=1;
swap(ls,rs);
}
void pushdown(int x)
{
if(flag[x])
{
reverse(x);
flag[ls]^=1,flag[rs]^=1;
flag[0]=0;
}
}
int newnode()
{
cnt++;
son[cnt][0]=son[cnt][1]=fa[cnt]=0;
return cnt;
}
void pushpath(int x)
{
for(top=0;!isroot(x);x=fa[x])stack[++top]=x;
stack[++top]=x;
for(int i=top;i;i--)pushdown(stack[i]);
}
void rotate(int x)
{
int y=fa[x],z=fa[y],i=is(x),t=son[x][!i];
if(!isroot(y))joint(x,z,is(y));
else fa[x]=z;
joint(t,y,i),joint(y,x,!i);
fa[0]=son[0][0]=son[0][1]=0;
}
void splay(int x)
{
pushpath(x);
int y,z;
while(!isroot(x))
{
y=fa[x],z=fa[y];
if(isroot(y)){rotate(x);break;}
rotate(is(x)==is(y)?y:x),rotate(x);
}
}
void access(int x)
{
int p=0;
while(x)
{
splay(x);
rs=p,p=x,x=fa[x];
}
}
void makeroot(int x)
{
access(x);
splay(x);
flag[x]=1;
pushdown(x);
}
void link(int x,int y)
{
makeroot(x);
fa[x]=y;
}
void cut(int x,int y)
{
makeroot(y);
access(x);
splay(x);
ls=fa[y]=0;
}
int findroot(int x)
{
while(fa[x])x=fa[x];
return x;
}
}lct;
int main()
{
// freopen("test.in","r",stdin);
int i,a,b;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)pos[i]=lct.newnode();
for(i=1;i<=m;i++)
{
scanf("%s",ttt);
scanf("%d%d",&a,&b);
if(ttt[0]=='C')lct.link(pos[a],pos[b]);
else if(ttt[0]=='D')lct.cut(pos[a],pos[b]);
else
{
if(lct.findroot(pos[a])==lct.findroot(pos[b]))puts("Yes");
else puts("No");
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BZOJ2049][SDOI2008]Cave동굴탐사LCT누드문제모형문제수조판수조, 적어도 현재 나는 수조만 쓰고 지침은 쓰지 않는다. LCT 같은 건 말 안 할 거야. 엉망진창이야. 어차피 이 편은 자용이야. 마찬가지로 이 블로그를 보는 사람들은 먼저 다른 곳에 가서 LCT를 배운 후에 나...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.