Submission #605942

#	Time	Username	Problem	Language	Result	Execution time	Memory
605942		GusterGoose27	Fireworks (APIO16_fireworks)	C++11	100 / 100	337 ms	80328 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

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

class hull {
public:
	ll init_val = 0;
	ll init_slope = 0;
	multiset<ll> changes;
	hull() {}
	void prune(ll length) {
		init_val += length;
		if (changes.empty()) {
			changes.insert(length);
			changes.insert(length);
			init_slope = -1;
			return;
		}
		while (changes.size() > -init_slope+1) changes.erase(changes.find(*changes.rbegin()));
		auto it = changes.rbegin();
		ll b2 = *it;
		changes.erase(changes.find(*it));
		it = changes.rbegin();
		ll b1 = *it;
		changes.erase(changes.find(*it));
		changes.insert(b1+length);
		changes.insert(b2+length);
	}
	void merge(hull *other) {
		init_val += other->init_val;
		init_slope += other->init_slope;
		for (ll v: other->changes) changes.insert(v);
		delete other;
	}
	ll size() {
		return changes.size();
	}
};

const ll MAXN = 3e5;
ll n, m;
vector<pii> edges[MAXN];
hull *hulls[MAXN];

void dfs(ll cur = 0) {
	hulls[cur] = new hull();
	for (pii e: edges[cur]) {
		ll next = e.first;
		dfs(next);
		hulls[next]->prune(e.second);
		if (hulls[cur]->size() > hulls[next]->size()) hulls[cur]->merge(hulls[next]);
		else {
			hulls[next]->merge(hulls[cur]);
			hulls[cur] = hulls[next];
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (ll i = 1; i < n+m; i++) {
		ll p, w;
		cin >> p >> w; p--;
		edges[p].push_back(pii(i, w));
	}
	dfs();
	hull *h = hulls[0];
	ll v = h->init_val;
	ll slope = h->init_slope;
	ll prev = 0;
	for (ll change: h->changes) {
		v += slope*(change-prev);
		slope++;
		if (slope == 0) break;
		prev = change;
	}
	cout << v << "\n";
}

Compilation message (stderr)

fireworks.cpp: In member function 'void hull::prune(ll)':
fireworks.cpp:22:25: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   22 |   while (changes.size() > -init_slope+1) changes.erase(changes.find(*changes.rbegin()));
      |          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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