Submission #1213884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213884		user736482	Tree (IOI24_tree)	C++20	100 / 100	135 ms	37368 KiB

tree

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll n,ans[1000007][2];
vector<ll>d[200007];
ll moj[200007],sz[200007];
bool czy[200007];
ll fnd(ll x){
    if(moj[x]==x)return x;
    return moj[x]=fnd(moj[x]);
}
void onion(ll x,ll y,ll c){
    x=fnd(x);y=fnd(y);
    if(sz[x]>sz[y])swap(x,y);
    moj[x]=y;
    sz[y]+=sz[x]-!czy[c];
    czy[c]=1;
}
void init(vector<int>p,vector<int>w){
    ll s=0;
    for(ll i : w)s+=i;
    n=p.size();
    for(ll i=0;i<200007;i++){moj[i]=i;sz[i]=1;}
    for(ll i=1;i<n;i++)d[p[i]].pb(i);
    for(ll i=0;i<n;i++){if(d[i].empty())ans[1][0]+=2*w[i];ans[1][1]+=w[i]*d[i].size();}
    ans[1][0]-=s;
    vector<pair<ll,ll>>v;
    for(ll i=0;i<n;i++)if(d[i].size())v.pb({w[i],i});
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    for(auto i : v){
        ll pm=0;
        ans[max(1LL,sz[fnd(i.ss)])][0]+=i.ff*sz[fnd(i.ss)];
        ans[max(1LL,sz[fnd(i.ss)])][1]-=i.ff;
        vector<ll>ak;
        ll aa=sz[fnd(i.ss)];
        for(ll j : d[i.ss]){
            ans[sz[fnd(j)]][1]-=i.ff;
            ans[sz[fnd(j)]][0]+=i.ff*sz[fnd(j)];
            pm+=sz[fnd(j)];
            onion(i.ss,j,i.ss);
        }
        ans[aa+pm-1][0]+=i.ff*(-pm-aa+1);
        ans[aa+pm-1][1]+=i.ff;
    }
    for(ll i=2;i<1000007;i++){
        ans[i][0]+=ans[i-1][0];
        ans[i][1]+=ans[i-1][1];
    }
}
ll query(int l,int r){
    return ans[r/l][0]*l+ans[r/l][1]*r;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 7 / 7
• Subtask 5: 11 / 11
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19