1103: [POI2007]大都市meg - #include <Seter> - using namespace Orz;
1103: [POI2007]大都市meg
http://www.zybbs.org/JudgeOnline/problem.php?id=1103
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 167895 | Seter | 1103 | Accepted | 13108 kb | 1632 ms | C/Edit | 1387 B | 2011-10-31 19:34:58 |
傻X题……那为什么要写题解呢……庆祝自己又一题RANK1呗……而且这次速度特别快……代码也很短，囧……
其实真正原因是为了纪念爆栈……用PAS的同学直接DFS递归就A掉了这题，我以为C也可以，没想到被坑了！！最后还是写了个栈，4行……唉……郁闷！
题解就是排出DFS序以后，W相当于查询一个点的权值，A相当于区间减1，就可以用树状数组维护。一开始忘了这样怎么维护了，就去看了看那时候R1的Tim神犇的代码，抄了下发现不行，结果发现我们的线段是不一样的……只好自己YY一个结果就对了- -！查询：S(x)；更新：I(b,1),I(a-1,-1)。
加了萎缩的i/o优化哦！33行～
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 | #include <stdio.h>#include <string.h>int n,m,a[250002],pos[250000][2],f[250000]={-1},k,s=0,stack[250000],tmp[10];char str[1000002],op[1400002],*p=str,*buf=op;inline void I(x,y){if(x)for(;x<=n;x+=x&-x)a[x]+=y;}inline S(x){int ans=0;for(;x;x-=x&-x)ans+=a[x];return ans;}struct edge{struct edge *next;int y;}*map[250000],st[500000],*q;_Bool v[250000];inline getint(){ int re=0; while(*p<'0'||*p>'9')if(!*++p)fread(p=str,1,1000000,stdin); for(;*p>='0'&&*p<='9';*p||fread(p=str,1,1000000,stdin))re=re*10+*p++-48; return re;}main(){ int i=-2,x,y; for(m=(n=getint())-1<<1;(i+=2)!=m;){ st[i].next=map[st[i^1].y=x=getint()-1]; st[i^1].next=map[st[i].y=y=getint()-1]; map[x]=st+i;map[y]=st+(i^1); }for(memset(f,-1,n<<2);s!=-1;)if(v[stack[s]])I(pos[stack[s--]][1]=k,-1); else{ v[x=stack[s]]=1;I(pos[x][0]=k++,1); for(q=map[x];q;q=q->next)if(q->y!=f[x])f[stack[++s]=q->y]=x; }for(m=getint()+n-1;m--;){ while(*p!='W'&&*p!='A')if(!*++p)fread(p=str,1,1000000,stdin); if(*p=='W'){ if(!(y=S(pos[getint()-1][0])))*buf++=48; else{ for(x=9;y;y/=10)tmp[x--]=y%10; while(++x!=10)*buf++=tmp[x]+48; }*buf++='\n'; }else(x=getint()-1)==f[y=getint()-1]?(I(pos[y][1],1),I(pos[y][0],-1)):(I(pos[x][1],1),I(pos[x][0],-1)); }return puts(op),0;} |
By Seter
评论 (0)