Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这个动态树写的太犀利了,顶起

Posted by xuhaoran510 at 2011-06-29 13:35:46 on Problem 1526
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator