比赛 20120718 评测结果 AATAAAAATT
题目名称 座位问题 最终得分 70
用户昵称 TBK 运行时间 0.417 s
代码语言 C++ 内存使用 6.89 MiB
提交时间 2012-07-18 11:21:51
显示代码纯文本
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <set>
#include <algorithm>
#define MAXN 0x7fffffff
using namespace std;
int a[100001],b,c,d,r[100001],p[1000000],q,tail=0,k[100001],l=1,t,s;
struct fun
{
	int x,y;
}f[200000];
bool bo[100001];
int Compare( const void *a , const void *b )
{
	struct fun *c = (struct fun *)a;
	struct fun *d = (struct fun *)b;
	if (c->x != d->x) return c->x - d->x;
		else return c->y - d->y;
}
int main(void)
{   
    freopen("seat.in","r",stdin);
    freopen("seat.out","w",stdout);
	scanf("%d",&b);
	for (c=0;c<b-1;c++) 
	{
		scanf("%d%d",&f[c].x,&f[c].y);
		f[c+b-1].x=f[c].y;
		f[c+b-1].y=f[c].x;
	}
	for (c=1;c<=b;c++) scanf("%d",&a[c]);
	qsort(f,2*b-2,sizeof(fun),Compare);
	for (c=1;c<2*b-2;c++)
		if (f[c].x!=f[c-1].x)
		{
			r[l]=c;
			l++;
		}
	p[q]=1;
	q++;
	tail=0;
	k[1]=-1;
	while (tail<q)
	{
		for (c=r[p[tail]-1];c<r[p[tail]];c++)
			if (k[f[c].y]==0) 
			{
				k[f[c].y]=p[tail];
				p[q]=f[c].y;
				q++;
			}
		tail++;
	}
	for (c=1;c<=b;c++)
	{
		t=a[c];
		bo[t]=true;
		s=0;
		while (t!=-1)
		{
			t=k[t];
			if (bo[t]==true) s++;
		}
		printf("%d\n",s);
	}
	fclose(stdin);
    fclose(stdout);
    return 0;
}