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