Submission #593985

#	Time	Username	Problem	Language	Result	Execution time	Memory
593985		penguinhacker	Fireworks (APIO16_fireworks)	C++17	100 / 100	241 ms	73272 KiB

fireworks

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

#define ll long long
#define ar array

const int mxN=3e5;
int n, m;
vector<ar<int, 2>> adj[mxN];
ll yi[mxN], ys[mxN]; // y intercept and y intercept slope
priority_queue<ll> pq[mxN];

void dfs(int u=0) {
	for (auto [v, w] : adj[u]) {
		if (adj[v].empty()) {
			yi[v]=w, ys[v]=-1;
			pq[v].push(w);
			pq[v].push(w);
		} else {
			dfs(v);
			// shift container by w
			ll last=-1;
			while(ys[v]+(int)pq[v].size()>0) {
				last=pq[v].top();
				pq[v].pop();
			}
			assert(last!=-1&&pq[v].size());
			ll first=pq[v].top();
			pq[v].pop();
			yi[v]+=w;
			pq[v].push(first+w);
			pq[v].push(last+w);
		}
		yi[u]+=yi[v];
		ys[u]+=ys[v];
		if (pq[v].size()>pq[u].size())
			swap(pq[u], pq[v]);
		while(pq[v].size()) {
			pq[u].push(pq[v].top());
			pq[v].pop();
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=1; i<n+m; ++i) {
		int p, c;
		cin >> p >> c, --p;
		adj[p].push_back({i, c});
	}
	dfs();
	ll ans=yi[0], slope=ys[0];
	vector<ll> changes;
	while(pq[0].size()) {
		changes.push_back(pq[0].top());
		pq[0].pop();
	}
	reverse(changes.begin(), changes.end());
	ll last=0;
	for (int i=0; slope<0; ++i, ++slope) {
		assert(i<changes.size());
		ans+=(changes[i]-last)*slope;
		last=changes[i];
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from fireworks.cpp:1:
fireworks.cpp: In function 'int main()':
fireworks.cpp:64:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   assert(i<changes.size());
      |          ~^~~~~~~~~~~~~~~

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