QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#490507 | #8757. 图 | wcyQwQ | TL | 0ms | 0kb | C++14 | 2.0kb | 2024-07-25 15:29:15 | 2024-07-25 15:29:15 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct DSU {
int p[N];
DSU(int _n = 0) {
iota(p + 1, p + _n + 1, 1);
}
pair<int, int> find(int x) {
if (p[x] == x) return {x, 0};
auto [f, d] = find(p[x]);
return {f, d + 1};
}
void merge(int x, int y) {
auto px = find(x), py = find(y);
if (px.second > py.second) swap(px, py);
p[px.first] = py.first;
}
bool check(int x, int y) { return find(x).first == find(y).first; }
void print(int u, int v) {
auto pu = find(u), pv = find(v);
vector<int> uP, vP;
if (pu.second > pv.second) {
for (int i = 0; i < pu.second - pv.second; i++) {
uP.emplace_back(u);
u = p[u];
}
} else {
for (int i = 0; i < pv.second - pu.second; i++) {
vP.emplace_back(v);
v = p[v];
}
}
while (u != v) {
uP.emplace_back(u);
vP.emplace_back(v);
u = p[u], v = p[v];
}
reverse(vP.begin(), vP.end());
cout << uP.size() + vP.size() + 1 << ' ';
for (int x : uP) cout << x << ' ';
cout << u << ' ';
for (int x : vP) cout << x << ' ';
cout << '\n';
}
};
void solve() {
int n, m, k;
cin >> n >> m, k = (m + n - 2) / (n - 1);
vector<DSU> G;
vector<pair<int, int>> e(m);
for (auto &[u, v] : e) cin >> u >> v;
auto print = [&](int u, int v) {
cout << u << ' ' << v << '\n';
for (auto S : G) S.print(u, v);
};
for (auto [u, v] : e) {
int l = 0, r = (int)G.size() - 1, pos = -1;
while (l <= r) {
int m = (l + r) / 2;
if (G[m].check(u, v)) l = m + 1;
else pos = m, r = m - 1;
}
if (pos == -1) {
DSU S(n);
S.merge(u, v);
G.emplace_back(S);
if (G.size() == k) {
print(u, v);
return;
}
} else G[pos].merge(u, v);
}
vector<DSU>().swap(G);
}
int main() {
// freopen("1.in", "r", stdin);
cin.tie(0)->sync_with_stdio(0);
int T;
cin >> T;
while (T--) solve();
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
10000 2 20 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 20 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 20 1 2 2 1 1 2 1 2 2 1 2 1 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 20 1 2 2 1 2 1 1 2 1 2 1 2 2 1 1 2 2 ...
output:
2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2...