제출 #103264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103264		Noam527	Fireworks (APIO16_fireworks)	C++17	7 / 100	4 ms	384 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 = 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 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45