QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#546411	#5455. TreeScript	Sunlight9	WA	20ms	3820kb	C++20	1.4kb	2024-09-04 00:49:33	2024-09-04 00:49:33

Judging History

你现在查看的是最新测评结果

[2024-09-04 00:49:33]
评测

测评结果：WA
用时：20ms
内存：3820kb

查看

[2024-09-04 00:49:33]
提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;

    vector<vector<int> > edge(n + 1);
    vector<int> fa(n + 1);
    int st;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (x) {
            fa[i] = x;
            edge[x].push_back(i);
        } else {
            st = i;
        }
    }

    vector<int> num(n + 1), dep(n + 1), all(n + 1);
    auto dfs = [&](auto &&self, int u) -> void {
        dep[u] = dep[fa[u]] + 1;
        all[dep[u]]++;
        if (!edge[u].empty()) {
            num[dep[u]]++;
        }
        for (auto v : edge[u]) {
            self(self, v);
        }
    };

    int ans = 1;
    auto dfs1 = [&](auto &&self, int u) -> void {
        if (edge[u].empty()) return;
        if ((all[dep[u]] == 1 || num[dep[u]] > 1) && (int)edge[u].size() > 1) {
            ans++;
        }
        for (auto v : edge[u]) {
            self(self, v);
        }
    };

    dfs(dfs, st);
    dfs1(dfs1, st);

    // for (int i = 1; i <= 5; ++i) {
    //     cerr << num[i] << " num\n";
    // }

    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int _;
    cin >> _;
    while (_--) solve();

    return 0;
}
/*
2
3
0 1 2
7
0 1 2 2 1 4 1
*/
/*
1
4
0 1 2 2 
*/
/*
1
7
0 1 1 3 1 5 5
*/

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3624kb

input:

2
3
0 1 2
7
0 1 2 2 1 4 1

output:

1
2

result:

ok 2 number(s): "1 2"

Test #2:

score: -100

Wrong Answer

time: 20ms

memory: 3820kb

input:

1000
197
0 1 1 2 1 4 1 5 8 3 5 1 4 7 12 14 4 7 10 9 12 11 16 10 21 19 22 17 25 13 28 9 5 15 26 26 33 25 15 1 35 6 32 17 37 8 19 43 19 27 29 9 30 6 31 27 35 35 37 13 28 38 57 31 38 8 22 14 33 9 18 62 52 37 10 19 22 60 54 12 38 59 64 65 80 82 28 60 85 78 27 25 71 14 52 6 59 14 87 32 33 41 59 41 88 38 ...

output:

result:

wrong answer 1st numbers differ - expected: '4', found: '47'