Submission #933233

#	Time	Username	Problem	Language	Result	Execution time	Memory
933233		amirhoseinfar1385	Fireworks (APIO16_fireworks)	C++17	0 / 100	5 ms	20256 KiB

fireworks

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

void vorod(){
	int d;
	cin>>n>>d;
	n+=d;
	for(int 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<int>pq[maxn];
int val[maxn];
void add(int u,int x,int z){
	//cout<<"wtf: "<<u<<" "<<x<<endl;
	int nx=pq[u].top();
	pq[u].pop();
	int ps=pq[u].top();
	pq[u].push(nx);
	if(z==0){
		if(x<=nx){
			pq[u].pop();
			pq[u].push(x);
			return ;
		}
		return ;
	}
	pq[u].push(x);
}

void merge(int u,int v){
	int fu=u;
	if(pq[u].size()<pq[v].size()){
		swap(u,v);
	}
	int z=0;
	while(pq[v].size()>0){
		auto x=pq[v].top();
		pq[v].pop();
		//cout<<u<<" "<<v<<" "<<val[u]<<" "<<val[v]<<" "<<x<<" tof"<<endl;
		x+=val[v];
		x-=val[u];
		if(z<2){
			add(u,x,z);
			z++;
		}
		else{
			pq[u].push(x);
		}
	}
	if(u!=fu){
		swap(pq[u],pq[fu]);
		swap(val[u],val[fu]);
	}
}

void solve(int u,int len=0){
	if(u!=1){
		len+=par[u].second;
	}
	//cout<<"injy: "<<u<<" "<<len<<endl;
	for(auto x:adj[u]){
		solve(x,len);
		merge(u,x);
	}
	//cout<<"tamam: "<<u<<endl;
	if((int)adj[u].size()==0){
		pq[u].push(len);
		pq[u].push(len);
	}
	//cout<<"khor: "<<u<<endl;
	priority_queue<int>qp=pq[u];
	while(qp.size()>0){
		//cout<<qp.top()+val[u]<<" ";
		qp.pop();
	}
	//cout<<"\n";
	if(u!=1){
		int f=pq[u].top();
		pq[u].pop();
		int ff=pq[u].top();
		pq[u].pop();
		val[u]-=par[u].second;
		pq[u].push(ff+par[u].second);
		pq[u].push(f+par[u].second);
	}
	//cout<<"khor: "<<u<<endl;
	qp=pq[u];
	while(qp.size()>0){
		//cout<<qp.top()+val[u]<<" ";
		qp.pop();
	}
	//cout<<"\n";
	return ;
}

void khor(){
	//cout<<"suma: "<<sum<<" "<<val[1]<<endl;
	vector<long long>all;
	while((int)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;
	int sz=all.size();
	for(int 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);
	}
	cout<<res<<endl;
}	

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

Compilation message (stderr)

fireworks.cpp: In function 'void add(int, int, int)':
fireworks.cpp:25:6: warning: unused variable 'ps' [-Wunused-variable]
   25 |  int ps=pq[u].top();
      |      ^~

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