比赛 |
“Asm.Def战记之夏威夷”杯 |
评测结果 |
WWWWWWWWWW |
题目名称 |
Asm.Def的病毒 |
最终得分 |
0 |
用户昵称 |
咸鱼二号 |
运行时间 |
0.025 s |
代码语言 |
C++ |
内存使用 |
0.31 MiB |
提交时间 |
2015-11-06 09:05:28 |
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<stdio.h>
#include<cstdlib>
#include<iomanip> //cout<<setiosflags(ios::fixed)<<setprecision(2);
#include<ctime> //double a=(double)clock(); cout<<a<<endl;
#include<vector>
#include<queue>
using namespace std;
inline int read()
{
int x=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return ff*x;
}
int N,Q,t1,t2;
int lin[1010],len=0;
struct edge
{
int y,next;
}e[2010];
inline void insert(int xx,int yy)
{
e[++len].next=lin[xx];
lin[xx]=len;
e[len].y=yy;
}
int q[1010],head,tail,depth[1010],prev[1010];
bool vis[1010];
void bfs()
{
head=tail=0;
q[head]=1,depth[1]=1;
for(;head<=tail;head++)
{
for(int i=lin[q[head]];i;i=e[i].next)
{
if(!depth[e[i].y])
{
prev[e[i].y]=q[head];
depth[e[i].y]=depth[q[head]]+1;
q[++tail]=e[i].y;
}
}
}
}
void cross1(int a,int b)
{
memset(vis,0,sizeof(vis));
if(depth[a]<depth[b])
swap(a,b);
while(depth[a]!=depth[b])
{
vis[a]=1;
a=prev[a];
}
if(a==b)
return;
while(a!=b)
{
vis[a]=1,vis[b]=1;
a=prev[a],b=prev[b];
}
}
bool cross2(int a,int b)
{
if(depth[a]<depth[b])
swap(a,b);
while(depth[a]!=depth[b])
{
if(vis[a])
return 1;
a=prev[a];
}
if(a==b)
return 0;
while(a!=b)
{
if(vis[a]||vis[b])
return 1;
a=prev[a],b=prev[b];
}
return 0;
}
int main()
{
freopen("asm_virus.in","r",stdin);
freopen("asm_virus.out","w",stdout);
N=read(),Q=read();
for(int i=1;i<N;i++)
{
t1=read(),t2=read();
insert(t1,t2),insert(t2,t1);
}
bfs();
for(int i=1;i<=Q;i++)
{
t1=read(),t2=read();
cross1(t1,t2);
t1=read(),t2=read();
if(cross2(t1,t2))
printf("YES\n");
else
printf("NO\n");
}
fclose(stdin),fclose(stdout);
return 0;
}