QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#793990#5455. TreeScriptJustJie#WA 22ms3920kbC++201.3kb2024-11-30 08:34:232024-11-30 08:34:24

Judging History

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

  • [2024-11-30 08:34:24]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:3920kb
  • [2024-11-30 08:34:23]
  • 提交

answer

/***************************************************************************************************
 * author : Jie Chen (4th Year CS)
 * school : Rochester Institute of Technology
 * created: 11.29.2024 18:59:18
****************************************************************************************************/
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;

void work(int tc) {
    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        int p;
        cin >> p;
        if (i != 0) {
            p--;
            adj[p].push_back(i);
        }
    }

    auto dfs = [&](auto&& self, int u) -> int {
        int cur = 1;
        int add = 0;
        if (adj[u].size() > 1) {
            add = 1;
        }
        vector<int> g;
        for (int v : adj[u]) {
            g.push_back(self(self, v) + add);
        }
        if (add == 0) {
            return cur;
        }
        sort(g.rbegin(), g.rend());
        return max({cur, g[0] - 1, g[1]});
    };
    cout << dfs(dfs, 0) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (int t = 1; T--; t++) {
        work(t);
    }
}

// ~ JustJie

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
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: 22ms
memory: 3920kb

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:

4
4
3
4
3
4
4
5
4
4
4
4
5
5
3
4
4
4
1
5
5
1
5
4
5
4
5
3
4
5
2
5
4
2
5
4
3
3
3
4
4
4
1
3
3
4
5
5
4
4
4
2
4
5
5
4
3
4
4
4
5
4
3
4
4
4
3
4
5
4
4
5
5
4
4
5
2
3
4
1
1
5
5
3
3
4
4
5
4
5
4
4
4
4
3
4
3
1
4
4
5
4
4
6
5
5
3
3
5
3
4
3
3
3
4
3
3
2
4
4
3
5
3
5
3
3
4
4
5
4
5
4
4
4
4
2
5
4
4
3
2
3
3
2
5
4
3
2
4
5
...

result:

wrong answer 7th numbers differ - expected: '5', found: '4'