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