Submission #1243557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243557		alexander707070	Tree (IOI24_tree)	C++20	18 / 100	65 ms	20152 KiB

tree

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

int n;
bool vis[MAXN];

long long leaves[MAXN];
vector<int> v[MAXN];
long long cost[MAXN],ans;

long long L,R,sum[MAXN],dp[MAXN],L0,L1;
long long pref[MAXN],suff[MAXN];

vector< pair<long long,long long> > comps;

void dfs(int x){
    vis[x]=true;

    if(cost[x]==0){
        L0++; return;
    }

    if(v[x].empty()){
        L1++; return;
    }

	for(int i:v[x]){
		dfs(i);
	}
}

void init(vector<int> P, vector<int> W){
	n=int(P.size());

	for(int i=1;i<=n;i++)cost[i]=W[i-1];

	for(int i=1;i<P.size();i++){
		v[P[i]+1].push_back(i+1);
	}

	for(int i=1;i<=n;i++){
        if(!vis[i]){
            L0=L1=0;
            dfs(i);

            comps.push_back({L0+L1,L1});
        }
    }

    sort(comps.begin(),comps.end());
    for(int i=0;i<comps.size();i++){
        pref[i]=comps[i].second;
        if(i>0)pref[i]+=pref[i-1];
    }

    for(int i=comps.size()-1;i>=0;i--){
        suff[i]=comps[i].first+comps[i].second;
        suff[i]+=suff[i+1];
    }
}

long long query(int lt, int rt){
	L=lt; R=rt;

    int l=-1,r=comps.size(),tt;

    while(l+1<r){
        tt=(l+r)/2;

        if(comps[tt].first*L<=R){
            l=tt;
        }else{
            r=tt;
        }
    }

    long long s1=0,s2=0;
    if(r>0)s1=pref[r-1]*L;
    if(r<comps.size())s2=suff[r]*L - abs(r-int(comps.size()))*R;

    return s1+s2;
}

/*int main(){

	init({-1, 0, 0}, {1, 1, 1});
	cout<<query(1,1)<<"\n";

	cout<<query(1,2)<<"\n";

	return 0;
}*/

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