QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#323119#8134. LCA CountingWJHWA 4ms30860kbC++141004b2024-02-08 16:43:242024-02-08 16:43:25

Judging History

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

  • [2024-02-08 16:43:25]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:30860kb
  • [2024-02-08 16:43:24]
  • 提交

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'