比赛 |
“Asm.Def战记之夏威夷”杯 |
评测结果 |
WWWWWWWWWA |
题目名称 |
Asm.Def的病毒 |
最终得分 |
10 |
用户昵称 |
sxysxy |
运行时间 |
0.120 s |
代码语言 |
C++ |
内存使用 |
0.33 MiB |
提交时间 |
2015-11-06 09:40:10 |
显示代码纯文本
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
//#define dbg
#ifndef dbg
void set_file()
{
freopen("asm_virus.in", "r", stdin);
freopen("asm_virus.out", "w", stdout);
}
#endif
int N;
int Q;
int s,t;
bool xxx;
bool y;
#define MAXN (1001)
vector<int> adj[MAXN];
void rd()
{
int i;
int u,v;
scanf("%d %d", &N, &Q);
for(i = 1; i <= N-1; i++)
{
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
}
int d[MAXN];
bool vs1[MAXN];
int p1[MAXN];
void bfs1(int s, int t)
{
int u,v,i;
queue<int> q;
memset(vs1, false, sizeof(vs1));
memset(p1, 0, sizeof(p1));
//开启spfa
for(i = 1; i <= N; i++)
{
d[i] = 0x7fffffff;
vs1[i] = false;
}
q.push(s);
vs1[s] = true;
while(!q.empty())
{
u = q.front();
q.pop();
for(i = 0; i < adj[u].size(); i++)
{
v = adj[u][i];
if(d[v] > d[u]+1)
{
d[v] = d[u]+1;
p1[v] = u;
if(!vs1[v])
{
q.push(v);
vs1[v] = true;
}
}
}
vs1[u] = false;
}
}
bool vs2[MAXN];
int p2[MAXN];
void bfs2(int s, int t)
{
int u,v,i;
queue<int> q;
memset(vs2, false, sizeof(vs2));
memset(p2, 0, sizeof(p2));
//开启spfa
for(i = 1; i <= N; i++)
{
d[i] = 0x7fffffff;
vs2[i] = false;
}
q.push(s);
vs2[s] = true;
while(!q.empty())
{
u = q.front();
q.pop();
for(i = 0; i < adj[u].size(); i++)
{
v = adj[u][i];
if(d[v] > d[u]+1)
{
d[v] = d[u]+1;
p2[v] = u;
if(!vs2[v])
{
q.push(v);
vs2[v] = true;
}
}
}
vs2[u] = false;
}
}
bool nt[MAXN];
void judge(int s1, int t1, int s2, int t2)
{
memset(nt, false, sizeof(nt));
int p,q;
p = t1;
q = t2;
vector<int> l1;
vector<int> l2;
while(p != s1)
{
l1.push_back(p);
p = p1[p];
}
while(q != s2)
{
l2.push_back(q);
q = p2[q];
}
for(p = 0; p < l1.size(); p++)
{
for(q = 0; q < l2.size(); q++)
{
if(l1[p] == l2[q])
{
xxx = true;
goto ok;
}
}
}
ok:;
}
void solve()
{
int s1,t1,s2,t2;
int i;
for(i = 1; i <= Q; i++)
{
scanf("%d %d %d %d", &s1, &t1, &s2, &t2);
bfs1(s1, t1);
bfs2(s2, t2);
xxx = false;
judge(s1, t1, s2, t2);
if(xxx)
printf("YES\n");
else
printf("NO\n");
}
}
int main()
{
#ifndef dbg
set_file();
#endif
rd();
solve();
return 0;
}