Submission #933272

#	Time	Username	Problem	Language	Result	Execution time	Memory
933272		amirhoseinfar1385	Fireworks (APIO16_fireworks)	C++17	100 / 100	235 ms	85088 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
const long long maxn=300000+10;
vector<long long>adj[maxn];
pair<long long,long long>par[maxn];
long long n;
long long sum=0;

void vorod(){
	long long d;
	cin>>n>>d;
	n+=d;
	for(long long i=2;i<=n;i++){
		cin>>par[i].first>>par[i].second;
		adj[par[i].first].push_back(i);
		sum+=par[i].second;
	}
}
priority_queue<long long>pq[maxn];
priority_queue <long long,vector<long long>, greater<long long>>revpq[maxn];
long long val[maxn];
void add(long long u,long long x,long long z){
	long long ps=pq[u].top(),nx=revpq[u].top();
	if(z==0){
		if(x<=nx){
			pq[u].push(x);
		}
		else{
			pq[u].push(revpq[u].top());
			revpq[u].pop();
			revpq[u].push(x);
		}
	}
	else{
		if(x>=ps){
			revpq[u].push(x);
		}
		else{
			revpq[u].push(pq[u].top());
			pq[u].pop();
			pq[u].push(x);
		}
	}
}

void merge(long long u,long long v){
	long long fu=u;
	if(pq[u].size()+revpq[u].size()<pq[v].size()+revpq[u].size()){
		swap(u,v);
	}
	while(pq[v].size()>0){
		add(u,pq[v].top()+val[v]-val[u],0);
		pq[v].pop();
	}
	while(revpq[v].size()>0){
		add(u,revpq[v].top()+val[v]-val[u],1);
		revpq[v].pop();
	}
	if(u!=fu){
		swap(pq[u],pq[v]);
		swap(revpq[u],revpq[v]);
		swap(val[u],val[v]);
	}
}

void solve(long long u,long long len=0){
	if(u!=1){
		len+=par[u].second;
	}
	for(auto x:adj[u]){
		solve(x,len);
		merge(u,x);
	}
	if((long long)adj[u].size()==0){
		pq[u].push(len);
		revpq[u].push(len);
	}
	if(u!=1){
		val[u]-=par[u].second;
		long long hey=revpq[u].top();
		while(revpq[u].size()>0){
			revpq[u].pop();
		}
		revpq[u].push(hey+par[u].second);
		hey=pq[u].top();
		pq[u].pop();
		pq[u].push(hey+par[u].second);
	}
	return ;
}

void khor(){
	//cout<<"suma: "<<sum<<" "<<val[1]<<endl;
	vector<long long>all;
	while((long long)pq[1].size()>0){
		all.push_back(pq[1].top()+val[1]);
		//cout<<pq[1].top()+val[1]<<endl;
		pq[1].pop();
	}
	all.push_back(0);
	long long res=sum;
	long long sz=all.size();
	for(long long i=0;i<sz-1;i++){
		////cout<<"tof: "<<all[i]<<" "<<i<<" "<<(all[i]-all[i+1])*i<<endl;
		res-=(all[i]-all[i+1])*((i+1));
	}
	cout<<res<<endl;
}	

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	vorod();
	solve(1);
	khor();
}

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45