14752022-11-05 22:06:56peti1234Egyengetőcpp14Futási hiba 0/1003ms3384 KiB
#include <bits/stdc++.h>

using namespace std;
const int c=1000005;
long long ans;
int n, koz, si[c], db[c];
vector<int> sz[c];
bitset<c> dp;
void dfs(int a) {
    si[a]=1;
    int maxi=0;
    for (auto x:sz[a]) {
        dfs(x);
        maxi=max(maxi, si[x]);
        si[a]+=si[x];
    }
    if (!koz && 2*si[a]>=n) {
        for (auto x:sz[a]) {
            db[si[x]]++;
        }
        if (a!=1) {
            db[n-si[a]]++;
        }
        ans+=n;
        koz=a;
    } else {
        ans+=min(si[a], n-maxi);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i=2; i<=n; i++) {
        int x;
        cin >> x;
        sz[x].push_back(i);
    }
    dfs(1);
    dp[0]=1;
    for (int i=1; i<=n; i++) {
        while (db[i]>=3) {
            db[2*i]++;
            db[i]-=2;
        }
        for (int j=1; j<=db[i]; j++) {
            //cout << "fontos " << i << "\n";
            dp|=(dp<<i);
        }
    }
    for (long long ert=n/2; ert<=n; ert++) {
        if (dp[ert]) {
            ans+=ert*(n-1-ert);
            break;
        }
    }
    cout << ans << "\n";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Futási hiba3ms1260 KiB
2Futási hiba2ms1432 KiB
subtask20/20
3Futási hiba2ms1604 KiB
4Futási hiba2ms1728 KiB
5Futási hiba2ms1728 KiB
6Futási hiba2ms1976 KiB
7Futási hiba2ms2256 KiB
8Futási hiba2ms2332 KiB
subtask30/20
9Futási hiba2ms2236 KiB
10Futási hiba2ms2488 KiB
11Futási hiba2ms2732 KiB
12Futási hiba2ms2788 KiB
13Futási hiba2ms2852 KiB
14Futási hiba2ms3040 KiB
subtask40/20
15Futási hiba2ms2840 KiB
16Futási hiba2ms2980 KiB
17Futási hiba2ms2844 KiB
18Futási hiba2ms2912 KiB
19Futási hiba2ms3036 KiB
20Futási hiba2ms3168 KiB
subtask50/40
21Futási hiba2ms3148 KiB
22Futási hiba2ms3216 KiB
23Futási hiba2ms3128 KiB
24Futási hiba2ms3152 KiB
25Futási hiba2ms3284 KiB
26Futási hiba2ms3384 KiB