比赛 |
“Asm.Def战记之夏威夷”杯 |
评测结果 |
AAAAAAAAAA |
题目名称 |
Asm.Def的病毒 |
最终得分 |
100 |
用户昵称 |
Satoshi |
运行时间 |
0.338 s |
代码语言 |
C++ |
内存使用 |
0.33 MiB |
提交时间 |
2015-11-06 09:17:54 |
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define N 1010
using namespace std;
ifstream in("asm_virus.in");
ofstream out("asm_virus.out");
int n,Q;
vector<int> G[N];
int p[N]={0};
bool l[N]={0},vis1[N]={0},vis2[N]={0};
void read()
{
int i,u,v;
in>>n>>Q;
for(i=1;i<n;i++)
{
in>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
}
void BFS(int s)
{
int i,u,v;
queue<int> q;
for(i=1;i<=n;i++)
{
l[i]=0;
p[i]=i;
}
q.push(s);
while(!q.empty())
{
u=q.front();
q.pop();
l[u]=1;
for(i=0;i<G[u].size();i++)
{
v=G[u][i];
if(!l[v])
{
p[v]=u;
q.push(v);
}
}
}
}
void update1(int x,int y)
{
int i;
while(true)
{
vis1[y]=1;
if(y==x)break;
y=p[y];
}
}
void update2(int x,int y)
{
while(true)
{
vis2[y]=1;
if(y==x)break;
y=p[y];
}
}
bool check()
{
int i;
for(i=1;i<=n;i++)if(vis1[i]&&vis2[i])return 1;
return 0;
}
void work()
{
int i,j,s1,t1,s2,t2;
for(i=1;i<=Q;i++)
{
for(j=1;j<=n;j++)vis1[j]=vis2[j]=0;
in>>s1>>t1>>s2>>t2;
BFS(s1);
update1(s1,t1);
BFS(s2);
update2(s2,t2);
if(check())out<<"YES"<<endl;
else out<<"NO"<<endl;
}
}
int main()
{
read();
work();
return 0;
}