Submission #262008

#	Time	Username	Problem	Language	Result	Execution time	Memory
262008		amoo_safar	Fireworks (APIO16_fireworks)	C++17	0 / 100	8 ms	11264 KiB

fireworks

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int n, m;
vector<int> G[N];
int C[N];
priority_queue<ll> pq[N];

void DFS(int u){
	if(G[u].empty()){
		pq[u].push(C[u]);
		pq[u].push(C[u]);
		return ;
	}
	for(auto adj : G[u]){
		DFS(adj);
		if(pq[adj].size() > pq[u].size())
			swap(pq[u], pq[adj]);
		while(!pq[adj].empty()){
			pq[u].push(pq[adj].top());
			pq[adj].pop();
		}
	}
	for(int i = 0; i + 1 < (int) G[u].size(); i++)
		pq[u].pop();
	ll sn = pq[u].top();
	pq[u].pop();
	ll s0 = pq[u].top();
	pq[u].pop();

	pq[u].push(sn + C[u]);
	pq[u].push(s0 + C[u]);

	//cerr << u << ' ' << pq[u].size() << '\n';
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int p;
	ll Sum = 0;
	for(int i = 2; i <= n + m; i++){
		cin >> p >> C[i];
		G[p].pb(i);
		Sum += C[i];
	}
	//cerr << "#########\n";
	DFS(1);

	vector<ll> V;
	while(!pq[1].empty()){
		V.pb(pq[1].top());
		pq[1].pop();
	}
	//debug
	reverse(all(V));

	ll M = 1 - ((int) V.size());
	//debug(M);
	ll po = 0;
	while(M < 0){
		//cerr << M << ' ' << V[po + 1] - V[po] << '\n';
		Sum += M * (V[po + 1] - V[po]);
		po ++;
		M ++;
	}
	cout << Sum << '\n';
	return 0;
}

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