JSK31435 | 敌对势力

Portal

本 blog 最水的文章之一。题面藥丸。我就什么话也不说。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <queue>
#include <cstdio>
#include <bitset>
const int N=1e5+1;
std::bitset<100001> rec[2],tmp;
int n,m,fp,d[N],head[N],ver[N],nxt[N],f[N];
int read() {
int x=0,c=getchar();
while(c<48||c>57) c=getchar();
while(c>47&&c<58) {x=(x<<3)+(x<<1)+c-48;c=getchar();}
return x;
}
void link(int x,int y) {
ver[++fp]=y;nxt[fp]=head[x];head[x]=fp;
ver[++fp]=x;nxt[fp]=head[y];head[y]=fp;
}
void bfs() {
std::queue<int> q;q.push(1);int u,v;d[1]=1;
while(q.size()) {
u=q.front();q.pop();
for(int i=head[u];i;i=nxt[i]) {
v=ver[i];if(d[v]) continue;
d[v]=d[u]+1;f[v]=u;q.push(v);
}
}
}
void mark(int x,int y,int flag) {
rec[flag][x]=rec[flag][y]=1;
if(d[x]<d[y]) x^=y^=x^=y;
for(;d[x]!=d[y];x=f[x]) rec[flag][x]=1;
for(;x!=y;x=f[x],y=f[y]) rec[flag][x]=1;
rec[flag][x]=1;

}
int main() {
n=read();m=read();
for(int i=1;i<n;++i) link(read(),read());
bfs();
for(int i=0,a,b,c,d;i<m;++i) {
rec[0].reset();rec[1].reset();tmp.reset();
a=read();b=read();c=read();d=read();
mark(a,b,0);mark(c,d,1);
tmp=rec[0]&rec[1];
if(tmp.any()) printf("NO\n");
else printf("YES\n");
}
return 0;
}

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。