Submission #1178209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178209		alexander707070	Tree (IOI24_tree)	C++20	13 / 100	2097 ms	28580 KiB

tree

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

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

long long L,R,sum[MAXN],dp[MAXN];
pair<long long,long long> sol;

void dfs2(int x,long long times){
	if(sum[x]==L)return;
	times=min(times,sum[x]-L);

	if(w[x]>0 and cost[x]>cost[sol.first]){
		sol.first=x;
		sol.second=min(times,w[x]);
	}

	for(int i:v[x]){
		dfs2(i,times);
	}
}

void dfs3(int x,long long times){
	if(sum[x]==L)return;
	times=min(times,sum[x]-L);

	if(sol.first==0 or cost[x]<cost[sol.first]){
		sol.first=x;
		sol.second=times;
	}

	for(int i:v[x]){
		dfs3(i,times);
	}
}

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

	if(v[x].empty()){
		w[x]=sum[x]=L;
		dp[x]=w[x]*cost[x];
		return;
	}

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

		sum[x]+=sum[i];
		dp[x]+=dp[i];
	}

	if(sum[x]<=R)return;
	
	while(true){

		sol={0,0};
		dfs2(x,sum[x]-R);
		if(sol.first==0)break;

		long long rem=min(sum[x]-R,sol.second);

		int curr=sol.first;
		w[curr]-=rem; sum[curr]-=rem;
		
		dp[x]-=rem*cost[sol.first];

		while(curr!=x){			
			curr=parent[curr];
			sum[curr]-=rem;
		}

		if(sum[x]<=R)return;
	}

	while(true){
		sol={0,0};

		dfs3(x,sum[x]-R);

		long long rem=min(sum[x]-R,sol.second);

		int curr=sol.first;
		w[curr]-=rem; sum[curr]-=rem;
		dp[x]+=rem*cost[sol.first];

		while(curr!=x){

			curr=parent[curr];
			sum[curr]-=rem;
		}

		if(sum[x]<=R)return;
	}

}
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);
		parent[i+1]=P[i]+1;
	}
}

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

	solve(1);
	return dp[1];
}

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