题目大意:
两种操作
0:对一个点反色(白变黑,黑变白)
1:查询这个点到一号点这一条链上离一号点最近的黑点的编号
我没话说了……这道题我交了可能有几十次,调了两个多小时,和别人对拍,就是不知道哪里写错了……
最后逼得没办法重新写了一遍……AC……
蛋疼的SPOJ……
#include<cstdio> #define rep(i,a,b) for(int i=a,tt=b;i<=tt;++i) #define erep(i,e,x) for(int i=x;i;i=e[i].next) const int oo=1000000000,maxn=100008,maxm=maxn<<1; int n,m; int h[maxn],vis[maxn],d[maxn],col[maxn],q[maxn]; struct E { int next,node; }e[maxm]; struct T { int lc,rc,fa,val,key,idx; T(){val=key=oo;lc=rc=fa=idx=0;} #define lc(x) tree[x].lc #define rc(x) tree[x].rc #define fa(x) tree[x].fa #define val(x) tree[x].val #define key(x) tree[x].key #define idx(x) tree[x].idx }tree[maxn]; void add(int a,int b){static int tot=0;e[++tot].next=h[a];e[tot].node=b;h[a]=tot;} void Update(int x) { if(val(lc(x))<val(rc(x)))val(x)=val(lc(x)),idx(x)=idx(lc(x)); else val(x)=val(rc(x)),idx(x)=idx(rc(x)); if(key(x)<val(x))val(x)=key(x),idx(x)=x; } void Zig(int x) { int y=fa(x),z=fa(y); if(lc(z)==y)lc(z)=x;else if(rc(z)==y)rc(z)=x;fa(x)=z; fa(rc(x))=y;lc(y)=rc(x);rc(x)=y;fa(y)=x; Update(y); } void Zag(int x) { int y=fa(x),z=fa(y); if(lc(z)==y)lc(z)=x;else if(rc(z)==y)rc(z)=x;fa(x)=z; fa(lc(x))=y;rc(y)=lc(x);lc(x)=y;fa(y)=x; Update(y); } bool isRoot(int x){return lc(fa(x))!=x&&rc(fa(x))!=x;} void Splay(int x) { for(int y,z;!isRoot(x);) { y=fa(x);z=fa(y); if(isRoot(y)) if(lc(y)==x)Zig(x); else Zag(x); else if(lc(z)==y) if(lc(y)==x)Zig(y),Zig(x); else Zag(x),Zig(x); else if(rc(y)==x)Zag(y),Zag(x); else Zig(x),Zag(x); } Update(x); } void Expose(int x){for(int y=0;x;x=fa(x)){Splay(x);rc(x)=y;Update(x);y=x;}} void Build() { int l=1,r=1,x,y; q[l]=1;vis[1]=true; while(l<=r) { x=q[l++]; erep(i,e,h[x]) { y=e[i].node;if(vis[y])continue; vis[y]=true;q[++r]=y; fa(y)=x;idx(y)=y;d[y]=d[x]+1; } } } int main() { scanf("%d%d",&n,&m);int a,b; rep(i,1,n-1)scanf("%d%d",&a,&b),add(a,b),add(b,a); Build(); rep(i,1,m) { scanf("%d%d",&a,&b); if(a) { Expose(b);Splay(b); printf("%d\n",val(b)>=oo?-1:idx(b)); } else { Splay(b); if(col[b])col[b]=0,key(b)=oo; else col[b]=1,key(b)=d[b]; Update(b); } } return 0; }
您还没有登录,请您登录后再发表评论
RandomGoCode:算法,SPOJ,涂鸦...但是在Go中!
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
My solution for some spoj problems
Online Judge Problem solution VN.SPOJ
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
SPOJ 应对spoj.com的挑战
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
SPOJ( )上选定问题的解决方案
2.12 求 A B 的约数之和对 MOD 取模 . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.13 莫比乌斯反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.13.1 莫比乌斯...
SPOJ 解决来自难题
杨弋SPOJ做题表格
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
Spoj 用户工具基于 Django 的 Spoj 用户分析工具。 目前托管在 Google Appengine 上: ://spojtool.appspot.com/安装获取列出的包,并将它们放在指定的项目目录中。 为了安全,请修改 secret_key.py 中的 SECRET_KEY...
教程SPOJ HướngdẫnvàchiasẻlờigiảichocácProblemstrênvn.spoj.com。 发展 确保没有在计算机上安装Ruby sudo apt install ruby ruby-dev 安装jekyll主题或直接键入 gem install bundler jekyll 在gem中...
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
A platform which can host online programming competitions (much like codechef and spoj). API of Hackerearth was used for online compilation and execution of programmes. Technology Used : HTML,CSS,...
SPOJ-Solutions:SPOJ算法问题的解决方案
相关推荐
RandomGoCode:算法,SPOJ,涂鸦...但是在Go中!
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
My solution for some spoj problems
Online Judge Problem solution VN.SPOJ
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
SPOJ 应对spoj.com的挑战
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
SPOJ( )上选定问题的解决方案
2.12 求 A B 的约数之和对 MOD 取模 . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.13 莫比乌斯反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.13.1 莫比乌斯...
SPOJ 解决来自难题
杨弋SPOJ做题表格
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
Spoj 用户工具基于 Django 的 Spoj 用户分析工具。 目前托管在 Google Appengine 上: ://spojtool.appspot.com/安装获取列出的包,并将它们放在指定的项目目录中。 为了安全,请修改 secret_key.py 中的 SECRET_KEY...
教程SPOJ HướngdẫnvàchiasẻlờigiảichocácProblemstrênvn.spoj.com。 发展 确保没有在计算机上安装Ruby sudo apt install ruby ruby-dev 安装jekyll主题或直接键入 gem install bundler jekyll 在gem中...
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
A platform which can host online programming competitions (much like codechef and spoj). API of Hackerearth was used for online compilation and execution of programmes. Technology Used : HTML,CSS,...
SPOJ-Solutions:SPOJ算法问题的解决方案