比赛 20120718 评测结果 AAAAATTTTT
题目名称 座位问题 最终得分 50
用户昵称 Truth.Cirno 运行时间 5.274 s
代码语言 C++ 内存使用 2.39 MiB
提交时间 2012-07-18 10:07:58
显示代码纯文本
  1. #include <cstdio>
  2. #include <memory.h>
  3. using namespace std;
  4.  
  5. int ava=1,rec,way[200001],nextway[200001],ptow[100001];
  6. bool right[100001]={0},used[100001];
  7.  
  8. void addway(int x,int y)
  9. {
  10. int pos;
  11. pos=ptow[x];
  12. if (pos==0)
  13. {
  14. ptow[x]=ava;
  15. way[ava++]=y;
  16. }
  17. else
  18. {
  19. while (nextway[pos])
  20. pos=nextway[pos];
  21. nextway[pos]=ava;
  22. way[ava++]=y;
  23. }
  24. }
  25.  
  26. void findway(int s,int e,int c)
  27. {
  28. if (s==e)
  29. {
  30. rec=c;
  31. return;
  32. }
  33. used[s]=true;
  34. int poi;
  35. poi=ptow[s];
  36. while (poi)
  37. {
  38. if (!used[way[poi]])
  39. {
  40. findway(way[poi],e,c+right[s]);
  41. if (rec!=-1)
  42. return;
  43. }
  44. poi=nextway[poi];
  45. }
  46. used[s]=false;
  47. }
  48.  
  49. int main(void)
  50. {
  51. freopen("seat.in","r",stdin);
  52. freopen("seat.out","w",stdout);
  53. int i,n,x,y,tar;
  54. scanf("%d",&n);
  55. for (i=1;i<n;i++)
  56. {
  57. scanf("%d%d",&x,&y);
  58. addway(x,y);
  59. addway(y,x);
  60. }
  61. for (i=1;i<=n;i++)
  62. {
  63. memset(used,0,sizeof(used));
  64. rec=-1;
  65. scanf("%d",&tar);
  66. findway(1,tar,0);
  67. printf("%d\n",rec);
  68. right[tar]=1;
  69. }
  70. return(0);
  71. }