QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#228644#3869. Gastronomic Eventucup-team1004RE 2ms12044kbC++14935b2023-10-28 13:51:412023-10-28 13:51:42

Judging History

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

  • [2023-10-28 13:51:42]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:12044kb
  • [2023-10-28 13:51:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2.5e5+10;
int n,siz[N],mx[N],cnt[N];
ll ans;
vector<int>to[N];
bitset<N>f;
void dfs1(int u,int fa=0){
	siz[u]=1;
	for(int v:to[u])if(v^fa){
		dfs1(v,u);
		mx[u]=max(mx[u],siz[v]);
		siz[u]+=siz[v];
	}
}
void dfs2(int u,int fa=0,int d=0){
	ans+=d,siz[u]=1;
	for(int v:to[u])if(v^fa){
		dfs2(v,u,d+1);
		siz[u]+=siz[v];
	}
}
int main(){
	scanf("%d",&n);
	for(int i=2,x;i<=n;i++){
		scanf("%d",&x);
		to[x].push_back(i),to[i].push_back(x);
	}
	dfs1(1);
	int rt=1;
	for(int i=1;i<=n;i++){
		mx[i]=max(mx[i],n-siz[i]),rt=mx[i]<mx[rt]?i:rt;
	}
	dfs2(rt);
	for(int v:to[rt])cnt[siz[v]]++;
	for(int i=1;i<=n;i++)for(;cnt[i]>2;cnt[i]-=2)cnt[i*2]++;
	f[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=cnt[i];j++)f|=f<<i;
	}
	for(int i=(n-1)/2;~i;i--)if(f[i]){
		ans+=1ll*i*(n-1-i);break;
	}
	cout<<ans+n<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 11124kb

input:

5
1 2 2 2

output:

13

result:

ok single line: '13'

Test #2:

score: 0
Accepted
time: 2ms
memory: 12044kb

input:

10
1 2 3 4 3 2 7 8 7

output:

47

result:

ok single line: '47'

Test #3:

score: -100
Runtime Error

input:

1000000
1 2 3 4 5 6 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 35 38 39 40 40 39 43 38 45 35 35 34 34 34 33 52 53 54 55 56 56 58 56 60 60 60 63 56 65 65 55 54 53 70 71 72 71 74 70 76 77 78 79 76 81 82 70 84 70 70 53 88 89 90 91 90 89 94 95 96 94 89 88 100 ...

output:


result: