bzoj2049
가변
다른 건 폭력이죠.
코드:
#include
using namespace std;
const int N=400005;
char op[10];
int c[N][2],size[N],n,m,y,rev[N],x,t,next[N],fa[N];
int isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
void pushup(int x){size[x]=size[c[x][0]]+size[c[x][1]]+1;}
void pushdown(int x)
{
if (rev[x])
{
rev[x]^=1;rev[c[x][0]]^=1;rev[c[x][1]]^=1;
swap(c[x][0],c[x][1]);
}
}
void down(int x)
{
if (!isroot(x))down(fa[x]);
pushdown(x);
}
void rotate(int x)
{
int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;
if(!isroot(y))c[z][c[z][1]==y] = x;
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x)
{
down(x);
for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])
if (!isroot(y))rotate((c[y][0]==x)==(c[fa[y]][0]==y)?y:x);
}
void access(int x)
{
int t=0;
while(x)
{
splay(x);
c[x][1]=t;
t=x;x=fa[x];
}
}
int find(int x)
{
for (;fa[x];x=fa[x]);
return x;
}
void rever(int x){access(x);splay(x);rev[x]^=1;}
void cut(int x,int y){rever(x);access(y);splay(y);c[y][0]=fa[x]=0;}
void link(int x,int y){rever(x);fa[x]=y;splay(x);}
int main()
{
scanf("%d%d",&n,&m);
while (m--)
{
scanf("%s%d%d",&op,&x,&y);
if (op[0]=='D')cut(x,y);
if (op[0]=='C')link(x,y);
if (op[0]=='Q')
{
rever(x);
if (find(y)==x)puts("Yes");
else puts("No");
}
}
}
전재 대상:https://www.cnblogs.com/xuanyiming/p/8018128.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.