oj.uz

Submission #401620

# Submission time Handle Problem Language Result Execution time Memory
401620 2021-05-10T14:58:28 Z BERNARB01 Fireworks (APIO16_fireworks) C++17
7 / 100
 1 ms 204 KB 
#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, 0)[0] << '\n';
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Incorrect 1 ms 204 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Incorrect 1 ms 204 KB Output isn't correct
14 Halted 0 ms 0 KB -