poi2012 rendezvous

stupid_lulu posted @ 2013年3月26日 01:16 in poi , 2885 阅读

基圈上的外向树求lca。。。先预处理所有的环长,以及外向树内的lca,对每个询问,在一棵树上就直接求,在一个环上就先到根,再判断从哪个方向走,如果不在一个环上输出-1 -1。。。

另:lca不知哪写错了,求大神查错。。。

#include<cstdio>
#include<cmath>
#include<cstring>
int can[500001];
int ansx=0,ansy=0,n,p=0,ss=0,m,sum=0;
int d[500001],pos[500001],fa[500001];
int f[500001][20],root[500001];
int dis[500001],kind[500001],head[500001],next[1000001];
struct re{
	int u,v;
} a[1000001];
inline int max(int a,int b){return a>b? a:b;}
inline int min(int a,int b){return a<b? a:b;}
void getlca(int x,int y){
	ansx=0;  ansy=0;
	if (x==y) return;
	//printf("fu\n");
	if (dis[x]>dis[y]){
		int xx=dis[x]-dis[y];
		ansx=xx;
		int k=int(log2(n));
		while (k>=0){
			if (xx>=(1<<k)){
				x=f[x][k];
				xx-=(1<<k);
			}
			k--;
		}
	}else{
		int xx=dis[y]-dis[x];
		ansy=xx;
		//printf("%d\n",xx);
		int k=int(log2(n));
		while (k>=0){
			if (xx>=(1<<k)){
				y=f[y][k];
				xx-=1<<k;
			}
			k--;
		}
	}
	//printf("f2\n");
	if (x==y) return;
	//printf("ansx=%d ansy=%d\n",ansx,ansy);
	//printf("x\n");
	int k=int(log2(n)); 
	while (k>=0){
		//printf("%d %d %d %d %d\n",k,ansx,ansy,f[x][k],f[y][k]);
		if (f[x][k]!=f[y][k]&&f[x][k]!=0&&f[y][k]!=0){
			ansx+=1<<k;  ansy+=1<<k;
			x=f[x][k];  y=f[y][k];
		}
		k--;
	}
	ansx++;  ansy++;
}
void get(int x,int y){
	if (root[x]==root[y]){
		//printf("e\n");
		getlca(x,y);
		return;
	}
	if (kind[root[x]]!=kind[root[y]]) return;
	ansx=dis[x];  ansy=dis[y];
	x=root[x];  y=root[y];
	int t=kind[x];
	int len=d[t];
	int lx=pos[y]-pos[x];
	if (lx<0) lx+=len;
	int rx=pos[x]-pos[y];
	if (rx<0) rx+=len;
	//printf("len=%d px=%d py=%d\n",len,pos[x],pos[y]);
	//printf("ax=%d ay=%d tx=%d ty=%d\n",ansx,ansy,lx,rx);
	if (max(lx+ansx,ansy)<max(ansx,rx+ansy)){
		//printf("a1\n");
		ansx+=lx;
		return;
	}
	if (max(lx+ansx,ansy)>max(ansx,rx+ansy)){
		//printf("a2\n");
		ansy+=rx;
		return;
	}
	//printf("f1 %d %d\n",ansx,rx+ansy);
	//printf("f2 %d %d\n",ansx+lx,ansy);
	if (min(lx+ansx,ansy)<min(ansx,rx+ansy)){
		//printf("b1\n");
		ansx+=lx;
		return;
	}
	if (min(lx+ansx,ansy)>min(ansx,rx+ansy)){
		//printf("b2\n");
		ansy+=rx;
		return;
	}
	//printf("s\n");
	ansx+=lx;
}
void done(int i){
	root[i]=i;
	kind[i]=++ss;
	d[ss]++;
	pos[i]=++p;
	int j=fa[i];
	while (j!=i){
		//printf("j=%d %d\n",j,i);
		root[j]=j;
		kind[j]=ss;
		d[ss]++;
		pos[j]=++p;
		j=fa[j];
	}
}
void dfs(int i,int x){
	can[i]=x;
	int k=fa[i];
	if (can[k]==x){
		done(k);
		return;
	}
	if (can[k]) return;
	can[k]=x;
	dfs(k,x);
}
void dfs2(int i){
	can[i]=1;
	//printf("ii=%d\n",i);
	int x=int(log2(n));
	f[i][0]=fa[i];
	for (int j=1;j<=x;j++){
		f[i][j]=f[f[i][j-1]][j-1];
	}
	for (int j=head[i];j;j=next[j]){
		int k=a[j].v;
		if (root[k]||can[k]) continue;
		root[k]=root[i];
		dis[k]=dis[i]+1;
		dfs2(k);
	}
}
void build(int u,int v){
	a[++sum].u=u;
	a[sum].v=v;
	next[sum]=head[u];
	head[u]=sum;
}
int main(){
	//freopen("ran3c.in","r",stdin);
	//freopen("ran.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y;
	for (int i=1;i<=n;i++){
		scanf("%d",&x);
		build(x,i);  build(i,x);
		fa[i]=x;
	}
	for (int i=1;i<=n;i++){
		if (!can[i]) dfs(i,i);
		//printf("%d\n",can[i]);
	}
	//printf("d\n");
	memset(can,0,sizeof(can));
	for (int i=1;i<=n;i++){
		if (root[i]) dfs2(i);
	}
	//for (int i=1;i<=n;i++) printf("i=%d root=%d dis=%d pos=%d kind=%d\n",i,root[i],dis[i],pos[i],kind[i]);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		ansx=-1;  ansy=-1;
		get(x,y);
		printf("%d %d\n",ansx,ansy);
	}
}
Avatar_small
cleaning services 说:
2021年9月03日 20:38

A lot of people cannot digest the belief that expert products can finish the project in while less while 2 hours whilst you used to shell out your entire sparetime in cleanup your house. This is because it can be their job and they also follow a new systematic tactic, advanced tools, and innovative cleaning solutions for cleaning the house. You should glance at the amount involving work done but not time expended when deciding value.

Avatar_small
monthly cleaning ser 说:
2023年10月16日 22:46

Gasoline paintings add a whole lot of class to somewhat of a room as well as easily find plenty of stores which will sell reproductions in famous works of art. You can select the painting from your choice as well as get for custom remaking if necessary additionally, the manufacturer might mail them how to you. You'll find original works of art by modest known artists or simply paintings in photographs; an experience are various.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter