修仙录 3.29

原地爆炸

jzoj 6094 循环流

https://jzoj.net/senior/#contest/show/2687/0
竟然是特判题。

#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=10;int op,T,n,a,b;int main(){freopen("flow.in","r",stdin);freopen("flow.out","w",stdout);cin>>op>>T;while(T--){scanf("%d%d%d",&n,&a,&b);if(a+b<n){printf("0\n");continue;}if(a==1){printf("0\n");continue;}if(n==2){if(a%2){printf("0\n");continue;}if(!a&&b%2){printf("0\n");continue;}printf("1\n");continue;}if(a+b==n&&a!=n&&b!=n){printf("0\n");continue;}printf("1\n");}return 0;
}

jzoj 6096 森林

https://jzoj.net/senior/#contest/show/2687/2
逼迫我去学了LCT。
https://www.cnblogs.com/flashhu/p/8324551.html
其实就是维护直径+最长支链（所谓的三叉戟。）

#include
#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
const int MAXN=2e5+5;int T,n,ans,mxl,u=1,v=1;
int fa[MAXN],sz[MAXN],c[MAXN][2];
int lx[MAXN],rx[MAXN],mx[MAXN],re[MAXN];
int st[MAXN],top;
multiset<int>len[MAXN];void up(int x){int l=c[x][0],r=c[x][1];sz[x]=sz[l]+sz[r]+1;int y=len[x].empty()?0: *len[x].rbegin();lx[x]=max(lx[l],sz[l]+1+max(lx[r],y));rx[x]=max(rx[r],sz[r]+1+max(rx[l],y));mx[x]=max(max(mx[l],mx[r]),y);
}bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
}void Swap(int x){swap(c[x][0],c[x][1]),swap(lx[x],rx[x]),re[x]^=1;
}void down(int x){if(re[x]) Swap(c[x][0]),Swap(c[x][1]),re[x]=0;
}bool isrc(int x){return c[fa[x]][1]==x;
}void rotate(int x){int F=fa[x],FF=fa[F],d=isrc(x);fa[x]=FF;if(!isroot(F)) c[FF][c[FF][1]==F]=x;fa[c[x][d^1]]=F,c[F][d]=c[x][d^1];fa[F]=x,c[x][d^1]=F;up(F);up(x);
}void putd(int x){st[++top]=x;while(!isroot(x)) st[++top]=x=fa[x];while(top) down(st[top--]);
}void sply(int x){putd(x);for(int F=fa[x];!isroot(x);rotate(x),F=fa[x]){if(isroot(F)) continue;if(isrc(x)==isrc(F)) rotate(F);else rotate(x);}
}void access(int x){for(int y=0;x;y=x,x=fa[x]){sply(x);if(y) len[x].erase(len[x].find(lx[y]));if(c[x][1]) len[x].insert(lx[c[x][1]]);c[x][1]=y;up(x);}
}void makeroot(int x){access(x),sply(x),Swap(x);
}int qry(int x,int y){makeroot(x),access(y),sply(y);return sz[y];
}int ask(int x,int y){makeroot(x),access(y),sply(y);if(mx[y]) return mx[y]-1;return 0;
}void add(int x,int F){makeroot(F),fa[F]=x;len[x].insert(lx[F]);up(x);int l1=qry(x,u),l2=qry(x,v);if(l1<=l2&&l2>mxl) u=x,mxl=l2;if(l2<l1&&l1>mxl) v=x,mxl=l1;ans=mxl+ask(u,v)-1;
}int main(){freopen("forest.in","r",stdin);freopen("forest.out","w",stdout);cin>>T>>n;for(int i=1,x;i<n;i++){scanf("%d",&x);x^=ans;add(i+1,x);printf("%d\n",ans);}return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！