比赛 20120718 评测结果 AAAAATTTTT
题目名称 座位问题 最终得分 50
用户昵称 Truth.Cirno 运行时间 5.274 s
代码语言 C++ 内存使用 2.39 MiB
提交时间 2012-07-18 10:07:58
显示代码纯文本
#include <cstdio>
#include <memory.h>
using namespace std;

int ava=1,rec,way[200001],nextway[200001],ptow[100001];
bool right[100001]={0},used[100001];

void addway(int x,int y)
{
	int pos;
	pos=ptow[x];
	if (pos==0)
	{
		ptow[x]=ava;
		way[ava++]=y;
	}
	else
	{
		while (nextway[pos])
			pos=nextway[pos];
		nextway[pos]=ava;
		way[ava++]=y;
	}
}

void findway(int s,int e,int c)
{
	if (s==e)
	{
		rec=c;
		return;
	}
	used[s]=true;
	int poi;
	poi=ptow[s];
	while (poi)
	{
		if (!used[way[poi]])
		{
			findway(way[poi],e,c+right[s]);
			if (rec!=-1)
				return;
		}
		poi=nextway[poi];
	}
	used[s]=false;
}

int main(void)
{
	freopen("seat.in","r",stdin);
	freopen("seat.out","w",stdout);
	int i,n,x,y,tar;
	scanf("%d",&n);
	for (i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		addway(x,y);
		addway(y,x);
	}
	for (i=1;i<=n;i++)
	{
		memset(used,0,sizeof(used));
		rec=-1;
		scanf("%d",&tar);
		findway(1,tar,0);
		printf("%d\n",rec);
		right[tar]=1;
	}
	return(0);
}