Submission #647251

#	Time	Username	Problem	Language	Result	Execution time	Memory
647251		atom	Fireworks (APIO16_fireworks)	C++17	100 / 100	223 ms	63796 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;    
const int N=300010, M = 1e9 + 7;

ll n,m,a,b,plague[N],root[N],ans;

vector<int> edges[N];

priority_queue<ll> q[N];

void dfs(int u){

	root[u]=u;

	if(u>n){

		q[u].push(plague[u]); 
		q[u].push(plague[u]);
		return;

	}

	for(auto v:edges[u]){

		dfs(v);

		if(q[root[v]].size() > q[root[u]].size()) root[u]=root[v];

	}

	for(auto v : edges[u]) 
		if(root[v]!=root[u]){

			while(q[root[v]].size()){

				q[root[u]].push(q[root[v]].top()); 
				q[root[v]].pop();

		}

	}
	for (int i = 1; i < (int) edges[u].size(); i++) q[root[u]].pop();

	a=q[root[u]].top(); q[root[u]].pop(); b=q[root[u]].top(); q[root[u]].pop();

	a+=plague[u]; b+=plague[u]; q[root[u]].push(b); q[root[u]].push(a);

}


int main(){

	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m;
	m += n;
	for (int i = 2; i <= m; i++){

		cin>>a>>b;

		edges[a].push_back(i);

		plague[i]=b; ans+=b;

	}

	dfs(1);

	q[root[1]].pop(); 
	a=q[root[1]].top(); 
	q[root[1]].push(0); 
	b=0;

	while(q[root[1]].size() > 0){

		ans-=(a - q[root[1]].top()) * b;
		b++;
		a=q[root[1]].top(); 
		q[root[1]].pop();

	}

	cout<<ans << "\n";

	return 0;

}

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