Submission #401612

#	Time	Username	Problem	Language	Result	Execution time	Memory
401612		BERNARB01	Fireworks (APIO16_fireworks)	C++17	7 / 100	1 ms	204 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

struct E {
	long long x, e;
	E(long long _x, long long _e) {
		x = _x;
		e = _e;
	}
	bool operator<(const E& other) {
		if (x == other.x) {
			return e < other.e;
		}
		return x < other.x;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long n, m;
	cin >> n >> m;
	vector<vector<pair<long long, long long>>> g(n + m);
	for (long long i = 1; i < n + m; i++) {
		long long p, c;
		cin >> p >> c;
		g[p - 1].emplace_back(i, c);
	}
	function<array<long long, 3>(long long, long long, long long)> DFS = [&](long long u, long long p, long long val) {
		array<long long, 3> ret = {0, -1, -1};
		if (u && g[u].size() == 0) {
			ret = {0, val, val};
			return ret;
		}
		vector<E> events;
		for (pair<long long, long long> _p : g[u]) {
			long long v = _p.first, w = _p.second;
			if (v != p) {
				array<long long, 3> sub = DFS(v, u, w);
				ret[0] += sub[0];
				events.push_back(E(sub[1], 0));
				events.push_back(E(sub[2], 1));
			}
		}
		assert(!events.empty());
		sort(events.begin(), events.end());
		vector<long long> D(events.size());
		D[events.size() - 1] = 0;
		long long add = 0, len = 0;
		for (long long i = (long long) events.size() - 2; i >= 0; i--) {
			len = events[i + 1].x - events[i].x;
			D[i] = D[i + 1] + add * len;
			add += !events[i].e;
		}
		long long dist = 0, minDist = (long long) 4e18L;
		add = 0, len = 0;
		for (long long i = 0; i < (long long) events.size(); i++) {
			len = events[i].x - (i ? events[i - 1].x : events[i].x);
			dist += add * len;
			minDist = min(minDist, dist + D[i]);
			add += events[i].e;
		}
		ret[0] += minDist;
		add = 0, len = 0;
		add = 0; len = 0; dist = 0;
		for (long long i = 0; i < (long long) events.size(); i++) {
			len = events[i].x - (i ? events[i - 1].x : events[i].x);
			dist += add * len;
			long long curDist = dist + D[i];
			if (curDist == minDist && ret[1] == -1) {
				ret[1] = events[i].x;
			}
			if (ret[1] != -1 && curDist == minDist) {
				ret[2] = events[i].x;
			}
			add += events[i].e;
		}
		ret[1] += val;
		ret[2] += val;
		return ret;
	};
	cout << DFS(0, -1, 0)[0] << '\n';
	return 0;
}

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