Submission #107441

#	Time	Username	Problem	Language	Result	Execution time	Memory
107441		Noam527	Fireworks (APIO16_fireworks)	C++17	100 / 100	1020 ms	93436 KiB

fireworks

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

struct edge {
	int to, w;
	edge() {}
	edge(int tt, int ww) {
		to = tt;
		w = ww;
	}
};

struct func {
	multiset<ll> s;
	ll st;
	func() {
		clear();
	}
	void clear() {
		s.clear();
		s.insert(0);
		s.insert(0);
		st = 0;
	}
	void insert(ll x) {
		s.insert(x);
	}
	void upd(const func &a) {
		st += a.st;
		for (const auto &i : a.s)
			s.insert(i);
	}
	void shift(ll x) {
		st += x;
		vector<ll> v;
		if (s.size()) v.push_back(*prev(s.end())), s.erase(prev(s.end()));
		if (s.size()) v.push_back(*prev(s.end())), s.erase(prev(s.end()));
		while (v.size()) {
			s.insert(s.end(), v.back() + x);
			v.pop_back();
		}
	}
	void print() {
		cout << "s: ";
		for (const auto &i : s) cout << i << " "; cout << '\n';
		cout << "start: " << st << '\n';
	}
};

int n;
vector<vector<edge>> g;
vector<int> sz;

void dfs(int v, int pre, func &f) {
	int big = -1, sh;
	for (const auto &i : g[v])
		if (i.to != pre && (big == -1 || sz[big] < sz[i.to])) big = i.to, sh = i.w;
	if (big == -1) {
		f = func();
		return;
	}
	dfs(big, v, f);
	f.shift(sh);
	func f2;
	for (const auto &i : g[v]) {
		if (i.to != pre && i.to != big) {
			f2.clear();
			dfs(i.to, v, f2);
			f2.shift(i.w);
			f.upd(f2);
		}
	}
	for (const auto &i : g[v])
		if (i.to != pre && i.to != big)
			f.s.erase(prev(f.s.end()));
	if (OO) {
		cout << "finishing node " << v << '\n';
		f.print();
		cout << '\n';
	}
}

int dfs(int v = 0, int prev = 0) {
	sz[v] = 1;
	for (const auto &i : g[v])
		if (i.to != prev)
			sz[v] += dfs(i.to, v);
	return sz[v];
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int useless;
	cin >> n >> useless;
	n += useless;

	g.resize(n);
	for (int i = 1, p, w; i < n; i++) {
		cin >> p >> w;
		--p;
		g[p].push_back(edge(i, w));
		g[i].push_back(edge(p, w));
	}
	sz.resize(n);
	dfs();
	func f;
	dfs(0, 0, f);
	ll ans = f.st;
	ll pos = 0;
	ll slope = (ll)f.s.size() - 1;
	auto it = f.s.begin();
	while (slope > 0) {
		ans -= slope * (*it - pos);
		pos = *it;
		slope--;
		it++;
	}
	finish(ans);
}

Compilation message (stderr)

fireworks.cpp: In member function 'void func::print()':
fireworks.cpp:53:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : s) cout << i << " "; cout << '\n';
   ^~~
fireworks.cpp:53:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : s) cout << i << " "; cout << '\n';
                                             ^~~~

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