QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#323119 | #8134. LCA Counting | WJH | WA | 4ms | 30860kb | C++14 | 1004b | 2024-02-08 16:43:24 | 2024-02-08 16:43:25 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define db long double
using namespace std;
const int N=5e5+10;
int f[N],d[N];
vector<int> g[N],ye,w[N];
void dfs(int x,int fa){
for(auto it:g[x])if(it!=fa){
dfs(it,x);
d[x]=min(d[it]+1,d[x]);
}
if(d[x]==1e18) d[x]=1,ye.push_back(x);
}
void dfss(int x,int fa){
for(auto it:g[x]) if(it!=fa){
dfss(it,x);
w[x].push_back(-f[it]);
}
sort(w[x].begin(),w[x].end());
if(!w[x].size()) f[x]=1;
else if(w[x].size()==1) f[x]=-w[x][0];
else f[x]=-w[x][0]-w[x][1];
}
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++) d[i]=1e18;
for(int i=2;i<=n;i++){
int y;cin>>y;
g[y].push_back(i);
g[i].push_back(y);
}
dfs(1,0);
dfss(1,0);
int cnt=1;
for(int i=1;i<=ye.size();i++){
if(i==1){
cout<<1<<" ";continue;
}
if(i<=f[1]){
cnt+=2;
}
else cnt++;
cout<<cnt<<" ";
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// int T;cin>>T;
// while(T--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 29180kb
input:
7 1 1 2 4 2 2
output:
1 3 5 6
result:
ok 4 number(s): "1 3 5 6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 30416kb
input:
10 1 1 2 2 1 1 1 2 4
output:
1 3 5 6 7 8 9
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 29540kb
input:
10 1 2 2 4 5 6 1 2 4
output:
1 3 5 7 8
result:
ok 5 number(s): "1 3 5 7 8"
Test #4:
score: 0
Accepted
time: 4ms
memory: 30464kb
input:
10 1 2 3 3 3 5 6 4 9
output:
1 3 4
result:
ok 3 number(s): "1 3 4"
Test #5:
score: -100
Wrong Answer
time: 4ms
memory: 30860kb
input:
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 4 1 2 2 1 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 6 3 1 1 1 2 2 1 1 2 1 2 1 3 1 2 1 1 2 1 1 1 1 1 1 1 4 1 5 1 1 1 1 1 2 1 1 2 1 2 1 2 5 3 1 3 1 1 2 1 2 1 1 3 2 1 6 2 1 2 5 1 1 1 3 2 1 2 1 1 1 1 1...
output:
1 3 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 10...
result:
wrong answer 6th numbers differ - expected: '10', found: '9'