Submission #794783

#	Time	Username	Problem	Language	Result	Execution time	Memory
794783		kingfran1907	Fireworks (APIO16_fireworks)	C++14	100 / 100	383 ms	105340 KiB

fireworks

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;
const int maxn = 3e5+10;

int n, m;
int p[maxn], c[maxn];
vector< pair<int, int> > graph[maxn];
multiset< llint > s[maxn];
llint a[maxn], b[maxn];

void solve(int x) {
	//printf("solving: %d\n", x);
	for (auto iter : graph[x]) {
		int tren = iter.X;
		int cost = iter.Y;
		
		solve(tren);
		while (a[tren] > 1) {
			a[tren]--;
			b[tren] += *s[tren].rbegin();
			s[tren].erase(--s[tren].end());
		}
		
		b[tren] -= cost;
		if (tren > n) {
			a[tren] = 1;
			s[tren].insert(cost);
			s[tren].insert(cost);
		} else {
			llint a = *s[tren].rbegin();
			s[tren].erase(--s[tren].end());
			llint b = *s[tren].rbegin();
			s[tren].erase(--s[tren].end());
			
			s[tren].insert(a + cost);
			s[tren].insert(b + cost);
		}
		//printf("merging: %d (%lld %lld)\n", tren, a[tren], b[tren]);
		//for (auto iter : s[tren]) printf("%lld ", iter); printf("\n");
		
		a[x] += a[tren];
		b[x] += b[tren];
		if (s[x].size() < s[tren].size()) swap(s[x], s[tren]);
		for (auto iter : s[tren]) s[x].insert(iter);
	}
	//printf("solved: %d\n", x);
	//printf("%lld %lld\n", a[x], b[x]);
	//for (llint tren : s[x]) printf("%lld ", tren); printf("\n");
}

int main() {
	scanf("%d%d", &n, &m); m += n;
	for (int i = 2; i <= m; i++) {
		scanf("%d%d", p+i, c+i);
		graph[p[i]].push_back({i, c[i]});
	}
	
	solve(1);
	llint sol = b[1];
	while (a[1] > 0) {
		a[1]--;
		sol += *s[1].rbegin();
		s[1].erase(--s[1].end());
	}
	printf("%lld\n", sol);
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d%d", &n, &m); m += n;
      |  ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d%d", p+i, c+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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