QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#440245 | #8757. 图 | alpha1022 | WA | 58ms | 3832kb | C++14 | 1.6kb | 2024-06-13 14:16:38 | 2024-06-13 14:16:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
vector<int> fa;
UnionFind(int n) : fa(n, -1) {}
bool isRoot(int u) { return !~fa[u]; }
int find(int u) { return isRoot(u) ? u : fa[u] = find(fa[u]); }
bool isMerged(int u, int v) {
int fu = find(u), fv = find(v);
if (fu == fv) return 1;
return 0;
}
void merge(int u, int v) {
int fu = find(u), fv = find(v);
if (fu == fv) return ;
fa[fv] = fu;
}
};
void solve() {
int n, m, k; scanf("%d%d", &n, &m), k = (m + n - 1) / (n - 1);
vector<vector<vector<int>>> e(k, vector<vector<int>>(n));
vector<UnionFind> uf(k, n);
int s = -1, t = -1;
for (; m; --m) {
int u, v; scanf("%d%d", &u, &v), --u, --v;
int l = 0, r = k - 1, res = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (!uf[mid].isMerged(u, v)) r = mid - 1, res = mid;
else l = mid + 1;
}
if (res == k - 1) s = u, t = v;
uf[res].merge(u, v), e[res][u].push_back(v), e[res][v].push_back(u);
}
printf("%d %d\n", t + 1, s + 1);
for (int i = 0; i < k; ++i) {
vector<int> vec;
auto dfs = [&](auto &self, int u, int fa) -> bool {
if (u == t) { vec.push_back(t); return 1; }
for (int v : e[i][u])
if (v != fa && self(self, v, u)) { vec.push_back(u); return 1; }
return 0;
};
dfs(dfs, s, -1), printf("%d ", (int)vec.size());
for (int j = 0; j < vec.size(); ++j) printf("%d%c", vec[j] + 1, " \n"[j + 1 == vec.size()]);
}
}
int main() {
int T;
for (scanf("%d", &T); T; --T) solve();
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 58ms
memory: 3832kb
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:
0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
result:
wrong answer Integer 0 violates the range [1, 2] (test case 1)