913. Query on a tree II - #include <Seter> - using namespace Orz;
913. Query on a tree II
https://www.spoj.pl/problems/QTREE2/
| ID | DATE | USER | PROBLEM | RESULT | TIME | MEM | LANG |
|---|---|---|---|---|---|---|---|
| 5468277 | 2011-08-04 12:33:38 | Seter | Query on a tree II |
accepted edit run |
0.35 | 3.3M |
C |
用块状树水过QTREE以后就开始颓废于电影...今天花了一个小时终于A掉了QTREE2...
写的时候非常纠结...主要是结构体定义的变量多了一个老搞混...额
然后没有1Y就是个悲剧啊。st指针忘记初始化了！！！导致栈溢出！！！万一是比赛就OVER了！！！
方法是离线TARJAN求LCA。对于DIST直接输出dis[i]+dis[j]-2dis[lca[i,j]]。对于KTH则维护每个点向上1,2,4,8...个点，然后logn向上跳Orz...
TIP1:此题没有给出操作个数...我写的代码开了10000A了...可见操作数不是很多...N+Q还是挺合算的...
TIP2:logn向上跳这东西我用了个很久以前看到的二进制加速，即MultiplyDeBruijnBitPosition这个。具体可以看看M67大牛blog！
http://www.matrix67.com/blog/archives/3985
PS:谁来告诉我排名顶上那个0.15S的秒杀代码怎么写的...看MEM似乎是在线的啊。。在线的应该没离线的快啊...郁闷！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include <stdio.h>#define find(x) N[(unsigned)((((x)&(-(x)))*0x077CB531U))>>27]static const int N[32]={0,1,28,2,29,14,24,3,30,22,20,15,25,17,4,8,31,27,13,23,21,19,16,7,26,12,18,6,11,5,10,9};int n,qs[10000][4],qss,fmap[10000][14];typedef struct _edge{struct _edge *next;int t,y;}edge;edge map[10000],*tail[10000],starr[39998],qsmap[10000],*st;fa(x){return qsmap[x].y==x?x:(qsmap[x].y=fa(qsmap[x].y));}getint(){ int re=0,ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48; return re;}void make(i,f){ edge *p=map[i].next,*q=qsmap[i].next; for(qsmap[i].t=qsmap[f].t+1;q;q=q->next)if(qsmap[q->y].t!=-1)qs[q->t][3]=fa(q->y); for(fmap[i][0]=map[i].y=f;p;p=p->next)if(p->y!=f){ map[p->y].t=map[i].t+p->t; make(p->y,i);qsmap[p->y].y=i; }}main(){ int x,t,y,i,c; for(c=getint(),n=getint();c--;c&&(n=getint())){ for(st=starr+19998,i=0;i<n;i++)(tail[i]=map+i)->next=0; for(i=0;i<n-1;i++){ x=getint()-1; (tail[x]=tail[x]->next=starr+(i<<1))->y=y=getint()-1; (tail[y]=tail[y]->next=starr+(i<<1^1))->y=x; tail[x]->next=tail[y]->next=0; tail[x]->t=tail[y]->t=getint(); }for(qss=i=0;i<n;i++)(tail[i]=qsmap+i)->next=0,qsmap[qsmap[i].y=i].t=-1; for(getchar(),i=getchar();i!='O';getchar(),i=getchar()){ qs[qss][0]=x=getint()-1; (tail[x]=tail[x]->next=st++)->y=qs[qss][1]=y=getint()-1; (tail[y]=tail[y]->next=st++)->y=x; tail[x]->next=tail[y]->next=0; tail[x]->t=tail[y]->t=qss; qs[qss++][2]=(i=='T'?getint():0)-1; }for(make(i=0,0);i<13;i++)for(t=0;t<n;t++)fmap[t][i+1]=fmap[fmap[t][i]][i]; for(i=0;i<qss;i++){ if(qs[i][2]==-1)printf("%d\n",map[qs[i][0]].t+map[qs[i][1]].t-(map[qs[i][3]].t<<1)); else{ x=qsmap[qs[i][0]].t-qsmap[qs[i][3]].t; y=qsmap[qs[i][1]].t-qsmap[qs[i][3]].t; qs[i][2]<=x?(t=qs[i][2],x=qs[i][0]):(t=x+y-qs[i][2],x=qs[i][1]); for(;t;t^=1<<y)x=fmap[x][y=find(t)]; printf("%d\n",x+1); } }putchar('\n'); }return 0;} |
By Seter
评论 (0)