QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#228644 | #3869. Gastronomic Event | ucup-team1004 | RE | 2ms | 12044kb | C++14 | 935b | 2023-10-28 13:51:41 | 2023-10-28 13:51:42 |
Judging History
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;
}
詳細信息
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 ...