比赛 “Asm.Def战记之夏威夷”杯 评测结果 AAAAAAAAAA
题目名称 Asm.Def的病毒 最终得分 100
用户昵称 万千世界,吾为大主宰 运行时间 0.037 s
代码语言 C++ 内存使用 0.37 MiB
提交时间 2015-11-06 08:42:57
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<vector>
  6. #include<cstring>
  7. #include<deque>
  8. #include<map>
  9. #define ll long long
  10.  
  11. using namespace std;
  12. int be[1001],en[1001];
  13. int n,q;
  14. struct sd{
  15. int nex,to;
  16. }e[10001];int h[1001],tot=0,no=0;
  17. int fa[1001];
  18. void add(int x,int y){tot++;e[tot].nex=h[x];e[tot].to=y;h[x]=tot;}
  19. void dfs(int x,int faa)
  20. {
  21. be[x]=++no;fa[x]=faa;
  22. for(int i=h[x];i;i=e[i].nex)
  23. {
  24. if(e[i].to!=faa)
  25. {
  26. dfs(e[i].to,x);
  27. }
  28. }
  29. en[x]=++no;
  30. }
  31. bool vis[1001],vis2[1001];
  32. void find1(int x)
  33. {
  34. vis[x]=1;
  35. if(x==1)return;
  36. find1(fa[x]);
  37. }
  38. bool u;
  39. void find2(int x)
  40. {
  41. if(!vis[x])vis[x]=1;
  42. else if(!u)u=1;
  43. else vis[x]=0;
  44. if(x==1)return;
  45. find2(fa[x]);
  46. }
  47. void find3(int x)
  48. {
  49. vis2[x]=1;
  50. if(x==1)return;
  51. find3(fa[x]);
  52. }
  53. bool u2;
  54. void find4(int x)
  55. {
  56. if(!vis2[x])vis2[x]=1;
  57. else if(!u2)u2=1;
  58. else vis2[x]=0;
  59. if(x==1)return;
  60. find4(fa[x]);
  61. }
  62. int main()
  63. {
  64. freopen("asm_virus.in","r",stdin);
  65. freopen("asm_virus.out","w",stdout);
  66. scanf("%d%d",&n,&q);
  67. int x,y,x2,y2;
  68. for(int i=1;i<n;i++)
  69. {
  70. scanf("%d%d",&x,&y);
  71. add(x,y);add(y,x);
  72. }
  73. dfs(1,0);
  74. for(int i=1;i<=q;i++)
  75. {
  76. scanf("%d%d%d%d",&x,&y,&x2,&y2);
  77. u=0;u2=0;
  78. memset(vis,0,sizeof vis);
  79. memset(vis2,0,sizeof vis2);
  80. find1(x);find2(y);
  81. find3(x2);find4(y2);
  82. bool p=0;
  83. for(int j=1;j<=n;j++)
  84. if(vis[j]&&vis2[j])
  85. {
  86. p=1;break;
  87. }
  88. if(p)printf("YES\n");
  89. else printf("NO\n");
  90. }
  91. }