QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#785741#9743. 重心树ChuanhuaYu#WA 18ms13068kbC++171.6kb2024-11-26 19:00:472024-11-26 19:00:47

Judging History

This is the latest submission verdict.

  • [2024-11-26 19:00:47]
  • Judged
  • Verdict: WA
  • Time: 18ms
  • Memory: 13068kb
  • [2024-11-26 19:00:47]
  • Submitted

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)