比赛 “Asm.Def战记之夏威夷”杯 评测结果 WWWWWWWWWW
题目名称 Asm.Def的病毒 最终得分 0
用户昵称 Fmuckss 运行时间 0.475 s
代码语言 C++ 内存使用 4.22 MiB
提交时间 2015-11-06 10:45:41
显示代码纯文本
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define maxn 1005
using namespace std;
int n,q;
int lca[maxn][maxn];
int fa[maxn],anc[maxn];
bool vis1[maxn],vis2[maxn];
vector<int> qx[maxn];
void beg(int x){
	for(int i=1;i<=x;i++){
		fa[i]=i;
		anc[i]=i;
		vis1[i]=false;
		vis2[i]=false;
	}
}
int findfa(int a){
	return fa[a]=(fa[a]==a ? a:findfa(fa[a]));
}
void unionab(int a,int b){
	int faa=findfa(a),fba=findfa(b);
	if(faa!=fba){
		fa[a]=fba;
	}
}
struct que{
	int x1,y1,x2,y2;
	bool l;
}qs[maxn];
struct node{
	vector<int> ne;
}ns[maxn];
void tarjan(int i){
	vis1[i]=true;
	for(int j=0;j<ns[i].ne.size();j++){
		if(vis1[ns[i].ne[j]])continue;
		tarjan(ns[i].ne[j]);
		unionab(i,ns[i].ne[j]);
		anc[findfa(i)]=i;
	}
	vis2[i]=true;
	for(int j=0;j<qx[i].size();j++){
		if(vis2[qx[i][j]]){
			lca[i][qx[i][j]]=anc[findfa(qx[i][j])];
			lca[qx[i][j]][i]=lca[i][qx[i][j]];
		}
	}
}
void solve(){
	for(int i=1;i<=n;i++){
		beg(n);
		tarjan(i);
		for(int i=1;i<=q;i++){
			int x1=qs[i].x1,x2=qs[i].x2;
			int y1=qs[i].y1,y2=qs[i].y2;
			if(lca[x1][y1]==lca[x2][y2]){
				qs[i].l=true;
			}
		}
	}
	for(int i=1;i<=q;i++){
		if(qs[i].l){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}
}
void read(){
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n-1;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		ns[a].ne.push_back(b);
		ns[b].ne.push_back(a);
	}
	for(int i=1;i<=q;i++){
		int x1,y1,x2,y2;
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		qx[x1].push_back(y1);
		qx[x2].push_back(y2);
		qx[y1].push_back(x1);
		qx[y2].push_back(x2);
		qs[i].x1=x1;qs[i].x2=x2;
		qs[i].y1=y1;qs[i].y2=y2;
	}
}
int main(){
	freopen("asm_virus.in","r",stdin);
	freopen("asm_virus.out","w",stdout);
	read();
	solve();
	return 0;
}