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