比赛 |
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;
}