Submission #794257

#	Time	Username	Problem	Language	Result	Execution time	Memory
794257		IvanJ	Fireworks (APIO16_fireworks)	C++17	100 / 100	143 ms	58944 KiB

fireworks

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 3e5 + 5;

struct Data {
	ll a, b;
	priority_queue<ll> *s;
	
	Data operator +(Data d) {
		Data ret;
		ret.a = a + d.a;
		ret.b = b + d.b;
		if(s->size() > d.s->size()) {
			ret.s = s;
			while(d.s->size()) 	
				ret.s->push(d.s->top()), d.s->pop();
		} else {
			ret.s = d.s;
			while(s->size()) 
				ret.s->push(s->top()), s->pop();
		}
		return ret;
	}
	
	ll get_min() {
		while(a > 0)
			a--, b += s->top(), s->pop();
		return b;
	}
};

int n, m;
int p[maxn];
ll c[maxn];
Data D[maxn];
vector<pair<int, ll>> adj[maxn];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1;i < n + m;i++)
		scanf("%d%lld", p + i, c + i), p[i]--;
	
	for(int i = 0;i < n + m;i++) 
		D[i].a = 0, D[i].b = 0, D[i].s = new priority_queue<ll>;
	
	for(int i = n;i < n + m;i++) {
		D[i].a = 1, D[i].b = -c[i];
		D[i].s->push(c[i]);
		D[i].s->push(c[i]);
		D[p[i]] = D[p[i]] + D[i];
	}
	
	for(int i = n - 1;i > 0;i--) {
		while(D[i].a > 1) {
			D[i].a--;
			D[i].b += D[i].s->top();
			D[i].s->pop();
		}
		ll x = D[i].s->top();D[i].s->pop();
		ll y = D[i].s->top();D[i].s->pop();
		D[i].s->push(x + c[i]);
		D[i].s->push(y + c[i]);
		D[i].b -= c[i];
		D[p[i]] = D[p[i]] + D[i];
	} 
	printf("%lld\n", D[0].get_min());
	return 0;
}

Compilation message (stderr)

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

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