Submission #1178155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178155		alexander707070	Tree (IOI24_tree)	C++20	0 / 100	59 ms	21920 KiB

tree

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

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

long long L,R,sum[MAXN],dp[MAXN];

void dfs(int x){
	if(v[x].empty())leaves[x]=1;

	for(int i:v[x]){
		dfs(i);
		leaves[x]+=leaves[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);
	}

	dfs(1);
	sort(leaves+1,leaves+n+1);
}

void solve(int x){
	sum[x]=0;

	for(int i:v[x]){
		solve(i);
		sum[x]+=sum[i];
	}

	if(sum[x]>R){
		ans+=cost[x]*(sum[x]-R);
		sum[x]=R;
	}

	if(sum[x]<L){
		ans+=cost[x]*(L-sum[x]);
		sum[x]=L;
	}
}

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

	long long ans=leaves[n]*L;

	int l=1,r=n+1,tt;
	while(l+1<r){
		tt=(l+r)/2;
		if(leaves[tt]*L<=R){
			l=tt;
		}else{
			r=tt;
		}
	}

	long long big=n-l;
	ans+=leaves[n] + (big-1)*R - big*R;

	return ans;

	/*ans=0;
	solve(1);
	return ans;*/
}

/*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: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19