oj.uz

Submission #103264

# Submission time Handle Problem Language Result Execution time Memory
103264 2019-03-29T11:50:18 Z Noam527 Fireworks (APIO16_fireworks) C++17
7 / 100
 4 ms 384 KB 
#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 = 1;
const int OOO = 1;
using namespace std;

struct func {
	ll cost, st, en;
	func() {
		cost = st = en = 0;
	}
	func(ll c, ll s, ll e) {
		cost = c;
		st = s;
		en = e;
	}
	ll operator ()(ll x) const {
		if (x < st) return cost + st - x;
		if (en < x) return cost + x - en;
		return cost;
	}
};
func merge(const vector<func> &f) {
	vector<ll> pos;
	for (const auto &i : f) pos.push_back(i.st), pos.push_back(i.en);
	sort(pos.begin(), pos.end());

	ll st = pos[pos.size() / 2 - 1], en = pos[pos.size() / 2], cost = 0;
	for (const auto &i : f)
		cost += i(st);
	return func(cost, st, en);
}
struct edge {
	int to, w;
	edge() {}
	edge(int tt, int ww) {
		to = tt;
		w = ww;
	}
};

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

func dfs(int v = 0, int prev = -1) {
	vector<func> f;
	for (const auto &i : g[v])
		if (i.to != prev) {
			f.push_back(dfs(i.to, v));
			f.back().st += i.w;
			f.back().en += i.w;
		}
	if (!f.size()) return func();
	return merge(f);
}

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));
	}
	cout << dfs().cost << '\n';
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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