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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #include <iostream>
#include <cstdio>
#include <vector>
#define maxn 100010
using namespace std;
int n, m, k;
struct Edge {
int fr, to;
};
int fa[maxn], dis[maxn], dep[maxn], st[maxn], top;
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i, dep[i] = 1; }
int find(int x) { while (x != fa[x]) x = fa[x]; return x; }
int D(int x) {
int d = 0;
while (x != fa[x]) d ^= dis[x], x = fa[x];
return d;
}
bool merge(int x, int y, int d) {
int fx = find(x), fy = find(y);
if (fx == fy) return !d;
if (dep[fx] > dep[fy]) swap(fx, fy);
fa[fx] = fy; dis[fx] = d; st[++top] = fx;
if (dep[fx] == dep[fy]) ++dep[fy], st[top] *= -1;
return 1;
}
void undo(int _top) {
while (top > _top) {
int x = st[top--];
if (x < 0) x = -x, --dep[fa[x]];
fa[x] = x; dis[x] = 0;
}
}
#define lc i << 1
#define rc i << 1 | 1
vector<Edge> T[maxn * 4];
void update(int i, int l, int r, int L, int R, const Edge &v) {
if (l > R || r < L) return ;
if (L <= l && r <= R) return T[i].push_back(v);
int m = l + r >> 1;
update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
}
void query(int i, int l, int r) {
bool ok = 1; int m = l + r >> 1, _top = top;
for (auto t : T[i]) ok &= merge(t.fr, t.to, D(t.fr) ^ D(t.to) ^ 1);
if (!ok) {
for (int i = l; i <= r; ++i) cout << "No\n";
return undo(_top);
}
if (l == r) return (cout << (ok ? "Yes" : "No") << "\n", undo(_top));
query(lc, l, m); query(rc, m + 1, r);
undo(_top);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> k; init_fa(n);
for (int i = 1; i <= m; ++i) {
int x, y, l, r; cin >> x >> y >> l >> r;
if (l == r) continue; ++l;
update(1, 1, k, l, r, { x, y });
} query(1, 1, k);
return 0;
}
|