Submission #377660

#	Time	Username	Problem	Language	Result	Execution time	Memory
377660		LucaDantas	Fireworks (APIO16_fireworks)	C++17	0 / 100	9 ms	11244 KiB

fireworks

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

#define int long long
#define pb push_back

constexpr int maxn = 2e5+10;

vector<int> g[maxn];
priority_queue<long long> changes[maxn];
int c[maxn], start_slope[maxn], n;
long long start_y[maxn];

void combine(int a, int b) {
	auto& q = changes[a];
	start_y[a] += start_y[b];
	start_slope[a] += start_slope[b];
	for(; changes[b].size(); changes[b].pop())
		q.push(changes[b].top());
	while((int)q.size() > -start_slope[a] + 1)
		q.pop();
}

void dfs(int u) {
	if(u >= n) {
		start_slope[u] = -1;
		start_y[u] = c[u];
		changes[u].push((long long)c[u]);
		changes[u].push((long long)c[u]);
	} else {
		int big = g[u][0];
		for(int v : g[u]) {
			if(changes[v].size() > changes[big].size())
				big = v;
			dfs(v);
		}
		swap(changes[u], changes[big]);
		start_slope[u] = start_slope[big];
		start_y[u] = start_y[big];
		for(int v : g[u])
			if(v != big) combine(u, v);
		start_y[u] += (long long)c[u];
		auto& q = changes[u];
		long long a = q.top(); q.pop();
		long long b = q.top(); q.pop();
		q.push(a + c[u]);
		q.push(b + c[u]);
	}
}

int32_t main() {
	int m; scanf("%lld %lld", &n, &m);
	for(int i = 1; i < n+m; i++) {
		int p; scanf("%lld %lld", &p, &c[i]);
		g[p-1].pb(i);
	}
	dfs(0);
	long long ans = start_y[0], last = 0;
	int slope = start_slope[0];
	auto& q = changes[0];
	vector<long long> opa;
	while(q.size())
		opa.pb(q.top()), q.pop();
	while(opa.size()) {
		ans += 1ll * slope * (opa.back() - last);
		last = opa.back(); opa.pop_back();
		++slope;
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

fireworks.cpp: In function 'int32_t main()':
fireworks.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |  int m; scanf("%lld %lld", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:54:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |   int p; scanf("%lld %lld", &p, &c[i]);
      |          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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