QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#440248 | #8757. 图 | alpha1022 | RE | 73ms | 3784kb | C++14 | 1.6kb | 2024-06-13 14:18:07 | 2024-06-13 14:18:08 |
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 - 2) / (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: 100
Accepted
time: 73ms
memory: 3784kb
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:
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 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 ...
result:
ok Answer correct. (10000 test cases)
Test #2:
score: -100
Runtime Error
input:
10000 5 20 2 1 2 5 5 3 3 1 4 5 1 4 4 3 4 5 3 5 5 4 2 3 5 2 3 4 3 5 1 4 4 3 4 2 2 1 1 3 5 1 5 20 4 2 1 3 1 2 4 5 2 4 3 1 5 3 5 1 4 5 4 3 2 4 1 4 4 3 5 2 1 2 3 5 1 5 4 1 3 4 4 3 5 20 1 4 1 3 1 5 5 1 4 5 3 4 4 5 2 3 1 2 2 4 4 5 4 5 2 4 2 5 4 2 4 3 4 2 2 5 2 1 3 1 5 20 2 5 2 3 4 5 4 2 3 4 2 1 5 4 2 5 2 ...