比赛 |
“Asm.Def战记之夏威夷”杯 |
评测结果 |
AAAAAAAAAA |
题目名称 |
Asm.Def的病毒 |
最终得分 |
100 |
用户昵称 |
Ezio |
运行时间 |
0.089 s |
代码语言 |
C++ |
内存使用 |
0.34 MiB |
提交时间 |
2015-11-06 11:31:46 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#define scafn scanf
#define For(st,ed,i) for(int i=st;i<=ed;++i)
#define Fordown(st,ed,i) for(int i=st;i>=ed;--i)
#define start(a,flag) memset(a,flag,sizeof(a));
#define ENDL cout<<endl;
using namespace std;
//-------------------------------------head------------------------------------------
vector<int> tu[1010];
int vis[1010][3];
int mark;
//-------------------------------------data------------------------------------------
int bfs(int st,int ed){
if(st==ed){
vis[st][0]=1;
vis[st][mark]=mark;
return 1;
}//遇到终点回溯
vis[st][0]=1;
vis[st][mark]=mark;//标记st点已经到了
int lg=tu[st].size();
for(int i=0;i<lg;++i){
if(vis[tu[st][i]][0]==0){//如果没到过
if(bfs(tu[st][i],ed)==1){
return 1;
}
}
}
vis[st][0]=0;
vis[st][mark]=0;
return 0;
}
//-----------------------------------function----------------------------------------
int main()
{
freopen("asm_virus.in","r",stdin);
freopen("asm_virus.out","w",stdout);
int n,q,z1,z2,flag;
scanf("%d%d",&n,&q);
For(2,n,i){
scanf("%d%d",&z1,&z2);
tu[z1].push_back(z2);
tu[z2].push_back(z1);
}
For(1,q,i){
For(0,n,i)vis[i][0]=vis[i][1]=vis[i][2]=0;
flag=1;
scanf("%d%d",&z1,&z2);
mark=1;
bfs(z1,z2);
For(0,n,i)vis[i][0]=0;
scanf("%d%d",&z1,&z2);
mark=2;
bfs(z1,z2);
For(1,n,i){
if(vis[i][1]==1&&vis[i][2]==2){
printf("YES\n");
flag=0;
break;
}
}if(flag)printf("NO\n");
}
return 0;
}