社区讨论
这题的叉点是什么
P5787【模板】线段树分治 / 二分图参与者 1已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo2divqh
- 此快照首次捕获于
- 2023/10/23 12:04 2 年前
- 此快照最后确认于
- 2023/11/03 12:11 2 年前
这份代码Subtask 2 T了
CPP#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cstdlib>
#include <bitset>
#include <deque>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 100005;
int fa[maxn << 1], sz[maxn << 1];
void init() {
for (int i = 1; i < maxn * 2; i++) fa[i] = i, sz[i] =1;
}
int find(int x) {
if (x == fa[x]) return fa[x];
return find(fa[x]);
}
void merge(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
sz[a] += sz[b];
fa[b] = a;
}
vector<pair<int, int> > e;
struct node {
vector<int> g;
} d[maxn << 2];
void update(int l, int r, int s, int t, int v, int p) {
if (l > r) return;
if (l <= s && t <= r) {
d[p].g.push_back(v);
return;
}
int mid = (s + t) >> 1;
if (l <= mid) update(l, r, s, mid, v, p << 1);
if (mid < r) update(l, r, mid + 1, t, v, p << 1 | 1);
}
int n, m, k, tot;
struct Opt {
int x, y;
};
stack<Opt> s;
void solve(int l, int r, int p) {
int now = s.size();
bool flag = 1;
for (int i : d[p].g) {
int u = e[i].first, v = e[i].second;
int fu = find(u), fv = find(v);
if (fu == fv) {
flag = 0;
for (int j = l; j <= r; j++) {
cout << "No" << "\n";
}
break;
}
merge(find(u + n), fv), merge(find(v + n), fu);
s.push((Opt){find(u + n), fv});
s.push((Opt){find(v + n), fu});
}
if (flag) {
if (l == r) {
cout << "Yes" << "\n";
} else {
int mid = (l + r) >> 1;
solve(l, mid, p << 1);
solve(mid + 1, r, p << 1 | 1);
}
}
while (s.size() > now) {
auto p = s.top();
s.pop();
sz[p.x] -= sz[p.y], fa[p.y] = p.y;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
init();
for (int i = 1; i <= m; i++) {
int x, y, l, r;
cin >> x >> y >> l >> r;
e.push_back(make_pair(x, y));
update(l + 1, r, 1, k, e.size() - 1, 1);
}
solve(1, k, 1);
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...