QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#539904#8134. LCA CountingPhantomThreshold#WA 1ms5668kbC++201.0kb2024-08-31 15:59:482024-08-31 15:59:50

Judging History

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

  • [2024-08-31 15:59:50]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5668kb
  • [2024-08-31 15:59:48]
  • 提交

answer

#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
//#define int long long
using namespace std;

const int maxn = 310000;

int n;
int fa[maxn];
vector<int>E[maxn];

int f[maxn];
multiset<int>S;
void dfs(const int x)
{
	if((int)E[x].size()==0)
	{
		f[x]=0;
		return;
	}
	if((int)E[x].size()==1)
	{
		auto y=E[x][0];
		f[x]=f[y];
		return;
	}
	
	for(auto y:E[x]) dfs(y);
	vector<int>V;
	for(auto y:E[x]) V.push_back(f[y]);
	sort(V.begin(),V.end());
	
	f[x]=V[0]+V[1]+1;
	for(int i=2,sz=(int)V.size();i<sz;i++)
		S.insert(V[i]);
}

signed main()
{
	ios_base::sync_with_stdio(false);
	
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		cin>>fa[i];
		E[fa[i]].push_back(i);
	}
	dfs(1);
	
	int ans=1;
	cout<<ans;
	S.insert(f[1]);
	auto it=S.end(); it--;
	while(it!=S.begin())
	{
		for(int j=0;j<(*it);j++)
		{
			ans+=2;
			cout<<' '<<ans;
		}
		ans+=1;
		cout<<' '<<ans;
		it--;
	}
	cout<<endl;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3876kb

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: -100
Wrong Answer
time: 1ms
memory: 5668kb

input:

10
1 1 2 2 1 1 1 2 4

output:

1 3 4 6 7 8 9

result:

wrong answer 3rd numbers differ - expected: '5', found: '4'