Submission #367407

#	Time	Username	Problem	Language	Result	Execution time	Memory
367407		alireza_kaviani	Fireworks (APIO16_fireworks)	C++11	100 / 100	282 ms	71020 KiB

fireworks

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = 3e5 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , m , ans , cur , C[MAXN];
vector<int> adj[MAXN];
priority_queue<ll> pq[MAXN];

void DFS(int v){
	for(int u : adj[v]){
		DFS(u);
		if(SZ(pq[u]) > SZ(pq[v]))	pq[v].swap(pq[u]);
		while(SZ(pq[u])){
			pq[v].push(pq[u].top());
			pq[u].pop();
		}
	}
	ll x = 0 , y = 0;
	for(int u : adj[v]){
		x = pq[v].top();
		pq[v].pop();
	}
	if(SZ(pq[v])){
		y = pq[v].top();
		pq[v].pop();
	}
	pq[v].push(y + C[v]);
	pq[v].push(x + C[v]);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n >> m; n += m;
	for(int i = 2 ; i <= n ; i++){
		int p; cin >> p >> C[i];
		adj[p].push_back(i); ans += C[i];
	}
	DFS(1);
	pq[1].push(0);
	while(SZ(pq[1]) > 1){
		ll x = pq[1].top(); pq[1].pop();
//		cout << x << endl;
		ans -= cur * (x - pq[1].top());
		cur++;
	}
//	cout << pq[1].top() << endl;
	cout << ans << endl;
	
    return 0;
}
/*

*/

Compilation message (stderr)

fireworks.cpp: In function 'void DFS(int)':
fireworks.cpp:34:10: warning: unused variable 'u' [-Wunused-variable]
   34 |  for(int u : adj[v]){
      |          ^

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