QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#784932 | #9751. 覆盖一棵树 | ChuanhuaYu# | WA | 9ms | 5704kb | C++17 | 1007b | 2024-11-26 16:21:40 | 2024-11-26 16:21:43 |
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;
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'