QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#784932#9751. 覆盖一棵树ChuanhuaYu#WA 9ms5704kbC++171007b2024-11-26 16:21:402024-11-26 16:21:43

Judging History

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

  • [2024-11-26 16:21:43]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:5704kb
  • [2024-11-26 16:21:40]
  • 提交

answer

// Author: Chuanhua Yu
// Time: 2024-11-26.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;

int n, tot;
int head[N], ver[N], nxt[N], h[N], th[N];

void add(int x, int y){
    ver[++tot] = y; nxt[tot] = head[x]; head[x] = tot;
}
void dfs(int x){
    if(head[x]) th[x] = n;
    for(int i = head[x]; i; i = nxt[i]){
        int y = ver[i];
        dfs(y);
        th[x] = min(th[x], th[y] + 1);
    }
    for(int i = head[x]; i; i = nxt[i])
        h[x] = max(h[x], th[ver[i]] + 1);
}
void solve(){
    tot = 1;
    cin >> n;
    for(int i = 1; i <= n; i++) head[i] = 0;
    for(int i = 2; i <= n; i++){
        int p; cin >> p;
        add(p, i);
    }
    dfs(1);
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, h[i]);
    cout << ans << '\n';
}

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: 0ms
memory: 5664kb

input:

2
8
1 2 3 2 5 1 7
8
1 2 3 4 5 6 7

output:

3
7

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 9ms
memory: 5704kb

input:

33428
10
1 2 3 3 4 6 7 7 9
10
1 2 3 4 5 6 7 8 8
8
1 2 3 4 5 6 7
8
1 2 3 4 4 6 7
4
1 2 3
3
1 2
3
1 1
9
1 2 3 4 5 6 7 8
2
1
3
1 2
10
1 2 3 4 5 6 7 8 9
3
1 2
2
1
10
1 2 3 4 5 6 7 8 9
2
1
5
1 2 2 4
8
1 2 3 4 5 6 7
5
1 2 3 3
2
1
5
1 2 3 4
3
1 2
9
1 2 3 4 5 6 6 8
9
1 2 3 4 5 6 7 8
9
1 2 3 4 5 5 7 8
8
1 2 ...

output:

4
8
8
8
8
8
8
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
...

result:

wrong answer 3rd lines differ - expected: '7', found: '8'