Submission #401618

#	Time	Username	Problem	Language	Result	Execution time	Memory
401618		BERNARB01	Fireworks (APIO16_fireworks)	C++17	Compilation error	0 ms	0 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

struct E {
	long long x;
	int e;
	E(long long _x, int _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);
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, long long>>> g(n + m);
	for (int i = 1; i < n + m; i++) {
		int p;
		long long c;
		cin >> p >> c;
		g[p - 1].emplace_back(i, c);
	}
	function<array<long long, 3>(int, long long)> DFS = [&](int u, 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<int, long long> _p : g[u]) {
			int v = _p.first;
			long long w = _p.second;
			if (v != p) {
				array<long long, 3> sub = DFS(v, 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 (int i = (int) 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) D[0];
		add = 0, len = 0;
		for (int i = 0; i < (int) events.size(); i++) {
			len = events[i].x - (i ? events[i - 1].x : events[i].x);
			dist += add * len;
			minDist = min(minDist, dist + D[i]);
			//cout << dist << " ";
			add += events[i].e;
		}
		//cout << '\n';
		ret[0] += minDist;
		add = 0, len = 0;
		//for (const auto& x : events) {
			//cout << x.x << " ";
		//}
		//cout << '\n';
		//for (const auto& x : events) {
			//cout << x.e << " ";
		//}
		//cout << '\n';
		//for (const auto& x : D) {
			//cout << x << " ";
		//}
		//cout << '\n';
		//cout << minDist << '\n';
		add = 0; len = 0; dist = 0;
		for (int i = 0; i < (int) events.size(); i++) {
			len = events[i].x - (i ? events[i - 1].x : events[i].x);
			dist += add * len;
			long long curDist = dist + D[i];
			//cout << curDist << " ";
			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;
		}
		//cout << '\n';
		ret[1] += val;
		ret[2] += val;
		//cout << u << " " << p << " " << val << " " << ret[0] << " " << ret[1] << " " << ret[2] << '\n';
		return ret;
	};
	cout << DFS(0, -1, 0)[0] << '\n';
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In lambda function:
fireworks.cpp:42:13: error: 'p' was not declared in this scope
   42 |    if (v != p) {
      |             ^
fireworks.cpp: In function 'int main()':
fireworks.cpp:104:22: error: no match for call to '(std::function<std::array<long long int, 3>(int, long long int)>) (int, int, int)'
  104 |  cout << DFS(0, -1, 0)[0] << '\n';
      |                      ^
In file included from /usr/include/c++/9/functional:59,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from fireworks.cpp:1:
/usr/include/c++/9/bits/std_function.h:683:5: note: candidate: '_Res std::function<_Res(_ArgTypes ...)>::operator()(_ArgTypes ...) const [with _Res = std::array<long long int, 3>; _ArgTypes = {int, long long int}]'
  683 |     function<_Res(_ArgTypes...)>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/std_function.h:683:5: note:   candidate expects 2 arguments, 3 provided