比赛 “Asm.Def战记之夏威夷”杯 评测结果 AAAAAAAAAA
题目名称 Asm.Def的病毒 最终得分 100
用户昵称 woca 运行时间 0.196 s
代码语言 C++ 内存使用 0.27 MiB
提交时间 2015-11-06 10:26:02
显示代码纯文本
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <fstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

bool ok;
int vis[2][1010];
vector <int> G[1010];
int d(int s,int t,int p){
    int h=0;
    if(s==t) return vis[p][s]=1;
    vis[p][s]=-1;
    for(int i=0;i<G[s].size();i++){
        if(vis[p][G[s][i]]==0){
            h=max(h,d(G[s][i],t,p));
        }
    }
    if(h==1)   
        vis[p][s]=1;
    else
        vis[p][s]=0;
    return h;
}

int main(){
    freopen("asm_virus.in","r",stdin);
    freopen("asm_virus.out","w",stdout);
    int n,q,u,v,s1,t1,s2,t2;
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    while(q--){
        memset(vis,0,sizeof(vis));ok=true;
        scanf("%d%d%d%d",&s1,&t1,&s2,&t2);
        d(s1,t1,0);
        d(s2,t2,1);
        for(int i=1;i<=n;i++){
            if(vis[0][i]==1&&vis[1][i]==1){  
                ok=false;break;
            }
        }
        if(ok)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}