QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#785741 | #9743. 重心树 | ChuanhuaYu# | WA | 18ms | 13068kb | C++17 | 1.6kb | 2024-11-26 19:00:47 | 2024-11-26 19:00:47 |
Judging History
answer
// Author: Chuanhua Yu
// Time: 2024-11-26.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
struct DSU {
vector<int> f, sz;
DSU(int n) : f(n + 1), sz(n + 1, 1) {
// 构建函数
iota(f.begin(), f.end(), 0);
}
int find(int x) {
// 寻找父亲,路径压缩
return f[x] == x ? x : f[x] = find(f[x]);
}
bool merge(int a, int b) {
// 合并两个节点
int fa = find(a), fb = find(b);
if (fa == fb)
return false;
if (sz[fb] > sz[fa])
swap(fa, fb);
f[fb] = fa;
sz[fa] += sz[fb];
return true;
}
bool same(int a, int b) {
// 判断两个点是否是一个集合
return find(a) == find(b);
}
};
int n, c[N];
vector<int> a[N], b[N];
priority_queue<int> q;
void solve(){
cin >> n;
for(int i = 1; i <= n; i++) b[i].clear();
for(int i = 1; i <= n; i++){
cin >> c[i];
a[i].resize(c[i]);
for(int& x:a[i]){ cin >> x; b[x].push_back(i); }
if(!c[i]) q.emplace(i);
}
DSU ds(n + 1);
while(!q.empty()){
int x = q.top(); q.pop();
for(int y:a[x]) {
y = ds.find(y);
cout << x << ' ' << y << '\n';
ds.merge(x, y);
}
for(int y:b[x]) if(!--c[y]) q.emplace(y);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while(T--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 13068kb
input:
2 4 2 3 4 1 3 0 0 3 1 3 1 3 0
output:
2 3 1 2 1 4 2 3 1 2
result:
ok Accepted (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 18ms
memory: 12972kb
input:
40000 3 2 2 3 0 0 2 1 2 0 4 2 4 3 1 4 0 0 5 1 3 2 5 4 1 5 0 0 4 3 2 3 4 0 0 0 2 1 2 0 2 1 2 0 5 1 2 3 3 4 5 0 0 0 2 1 2 0 2 1 2 0 5 4 2 3 4 5 0 0 0 0 4 1 2 2 3 4 0 0 5 2 5 4 1 5 1 4 0 0 2 1 2 0 5 1 2 3 3 4 5 0 0 0 5 2 2 3 0 2 4 5 0 0 5 2 5 4 1 5 1 4 0 0 5 2 2 4 2 3 5 0 0 0 4 1 3 1 4 1 4 0 4 2 4 3 1 ...
output:
1 2 1 3 1 2 2 4 1 2 1 3 3 5 2 3 2 4 1 3 1 2 1 3 1 4 1 2 1 2 2 3 2 4 2 5 1 2 1 2 1 2 1 2 1 3 1 4 1 5 2 3 2 4 1 2 3 4 2 5 1 2 1 3 1 2 2 3 2 4 2 5 1 2 3 4 3 5 1 2 1 3 3 4 2 5 1 2 1 3 2 3 2 5 1 2 1 4 3 4 2 3 1 3 2 4 1 2 1 3 2 3 1 2 3 5 2 4 1 2 1 3 1 2 2 3 1 2 3 4 3 5 2 3 1 3 1 2 3 4 2 3 1 3 4 5 2 4 1 4 ...
result:
wrong answer The index of the node i's father should less than i (test case 4)