| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这个动态树写的太犀利了,顶起In Reply To:据说此题可以用Link Cut Tree 做................附代码 Posted by:morenan at 2011-06-29 11:51:42 > #include<iostream>
> #include<stdio.h>
>
> #define FOR(i,l,r) for (i=l;i<=r;i++)
> #define MAXN 10100
> #define MAXM 100100
>
> using namespace std;
> int ca,sa,n;
>
> struct Link_Cut_Tree {
> int ki[MAXN][2],fa[MAXN];
> int pp[MAXN],cir[MAXN];
> void clear() {
> #define M(a) memset(a,0,sizeof(a))
> M(ki);M(fa);M(pp);M(cir);
> }
> int find_root(int now) {
> while (fa[now]) now=fa[now];
> return now;
> }
> void rotate(int now,bool kin) {
> int fp=fa[now],kp=ki[now][kin],kkp=ki[ki[now][kin]][kin^1];
> fa[now]=kp ;ki[kp ][kin^1 ]=now;
> fa[kp ]=fp ;ki[fp ][ki[fp][1]==now]=kp ;
> fa[kkp]=now;ki[now][kin ]=kkp;
> }
> void up(int now) {
> int root=find_root(now),i1,i2;
> if (root==now) return ;
> pp[now]=pp[root];pp[root]=0;
> while (fa[now]) {
> if (!fa[fa[now]]) {
> rotate(fa[now],ki[fa[now]][1]==now);return ;
> }
> i1=(ki[fa[now] ][1]==now );
> i2=(ki[fa[fa[now]]][1]==fa[now]);
> if (i1^i2) {
> rotate(fa[now] ,i1);rotate(fa[now],i2);
> } else {
> rotate(fa[fa[now]],i2);rotate(fa[now],i1);
> }
> }
> fa[0]=pp[0]=cir[0]=0;
> }
> void access(int now) {
> for (int pre=0;now;) {
> up(now);
> fa[ki[now][1]]=0;
> pp[ki[now][1]]=now;
> ki[now][1]=pre;
> fa[pre]=now;
> pp[pre]=0;
> pre=now;now=pp[now];
> }
> fa[0]=pp[0]=cir[0]=0;
> }
> void del(int now) {
> int i,j,k;
> access(now);up(now);
> for (i=now;ki[i][0];i=ki[i][0]) ;
> if (cir[i]) {
> if (now==i) {
> cir[i]=0;return ;
> }
> access(cir[i]);up(now);
> for (j=cir[i];fa[j] && fa[fa[j]];j=fa[j]) ;
> if (cir[i]==now || (fa[j]==now && ki[now][1]==j)) {
> pp[ki[now][0]]=cir[i];cir[i]=0;
> } else {
> access(now);up(now);
> }
> }
> fa[ki[now][0]]=0;ki[now][0]=0;
> }
> void ins(int now,int nex) {
> int i,j,k;
> access(nex);up(nex);
> for (i=now;fa[i] && fa[fa[i]];i=fa[i]) ;
> if (now==nex || (fa[i]==nex && ki[nex][0]==i)) {
> cir[now]=nex;return ;
> }
> pp[find_root(now)]=nex;
> }
> int ring(int now) {
> int i,j,k;
> access(now);up(now);
> for (i=now;ki[i][0];i=ki[i][0]) ;
> return cir[i]?9999:i;
> }
> } LCT;
>
> struct Event {
> int t,o,d;
> Event(int i1=0,int i2=0,int i3=0):
> t(i1),o(i2),d(i3) {}
> void update() {
> if (d==0) LCT.del(o);
> else LCT.ins(o,d);
> }
> friend bool operator < (Event e1,Event e2) {
> return e1.t<e2.t || (e1.t==e2.t && e1.d<e2.d);
> }
> } ev[MAXM];
>
> void init() {
> LCT.clear();n=0;
> }
>
> void qsort(int l,int r) {
> int i=l,j=r;Event k=ev[(l+r)>>1];
> while (i<=j) {
> for (;k<ev[i];i++) ;
> for (;ev[j]<k;j--) ;
> if (i<=j) swap(ev[i++],ev[j--]);
> }
> if (i<r) qsort(i,r); if (j>l) qsort(l,j);
> }
>
> int main() {
> int i,j,k,S,L;
> printf("CALL FORWARDING OUTPUT\n");
> for (scanf("%d",&ca);init(),ca;ca--) {
> printf("SYSTEM %d\n",++sa);
> while (scanf("%d",&i)!=EOF && i) {
> scanf("%d%d%d",&S,&L,&j);
> ev[++n]=Event(S ,i,j);
> ev[++n]=Event(S+L+1,i,0);
> }
> qsort(1,n);
> while (scanf("%d",&i)!=EOF && i!=9000) {
> scanf("%d",&j);
> while (n && ev[n].t<=i)
> ev[n--].update();
> printf("AT %04d CALL TO %04d RINGS %04d\n",i,j,LCT.ring(j));
> }
> }
> printf("END OF OUTPUT\n");
> return 0;
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator