제출 #1213875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213875		user736482	트리 (IOI24_tree)	C++20	7 / 100	70 ms	37292 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){
    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;
    ans[1][0]-=n;
    ans[1][1]+=n-1;
    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)]-1)][0]+=sz[fnd(i.ss)];
        ans[max(1LL,sz[fnd(i.ss)]-1)][1]--;
        vector<ll>ak;
        ll aa=sz[fnd(i.ss)];
        for(ll j : d[i.ss]){
            ans[sz[fnd(j)]][1]--;
            ans[sz[fnd(j)]][0]+=sz[fnd(j)];
            pm+=sz[fnd(j)];
            onion(i.ss,j,i.ss);
        }
        ans[aa+pm-1][0]+=(-pm-aa+1);
        ans[aa+pm-1][1]++;
    }
    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: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 7 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19