QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#552136 | #8757. 图 | caijianhong | WA | 78ms | 3612kb | C++23 | 1.9kb | 2024-09-07 20:48:21 | 2024-09-07 20:48:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
struct dsu {
vector<int> fa, siz;
vector<vector<int>> g;
dsu() = default;
explicit dsu(int n) : fa(n), siz(n, 1), g(n) { iota(fa.begin(), fa.end(), 0); }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool merge(int x, int y) {
if (find(x) == find(y)) return false;
g[x].push_back(y), g[y].push_back(x);
x = find(x), y = find(y);
if (siz[x] < siz[y]) swap(siz[x], siz[y]);
fa[y] = x, siz[x] += siz[y];
return true;
}
vector<int> getpath(int st, int ed) {
vector<int> stk, ans;
auto dfs = [&](auto&& dfs, int u, int fa) -> void {
stk.push_back(u);
if (ed == u) ans = stk;
for (int v : g[u]) if (v != fa) dfs(dfs, v, u);
stk.pop_back();
};
dfs(dfs, st, 0);
return ans;
}
};
int n, m, k;
int mian() {
cin >> n >> m;
k = (m + n - 2) / (n - 1);
vector<dsu> vec(k, dsu{n});
int stu = -1, stv;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
--u, --v;
int l = 0, r = k - 1, ans = k - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (vec[mid].find(u) == vec[mid].find(v)) l = mid + 1;
else r = mid - 1, ans = mid;
}
vec[ans].merge(u, v);
if (ans == k - 1) tie(stu, stv) = tie(u, v);
}
if (stu == -1) cout << -1 << endl;
else {
cout << stu + 1 << " " << stv + 1 << endl;
for (int i = 0; i < k; i++) {
auto path = vec[i].getpath(stu, stv);
cout << path.size();
for (int x : path) cout << " " << x + 1;
cout << endl;
}
}
return 0;
}
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
int t;
cin >> t;
while (t--) mian();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 78ms
memory: 3612kb
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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer Integer 0 violates the range [1, 21] (test case 1)