oj.uz

답안 #107439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107439 2019-04-24T10:20:39 Z Noam527 Fireworks (APIO16_fireworks) C++17
0 / 100
 2 ms 512 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 = 0;
const int OOO = 1;
using namespace std;

struct edge {
	int to, w;
	edge() {}
	edge(int tt, int ww) {
		to = tt;
		w = ww;
	}
};

struct func {
	multiset<ll> s;
	ll st;
	func() {
		clear();
	}
	void clear() {
		s.clear();
		s.insert(0);
		s.insert(0);
		st = 0;
	}
	void insert(ll x) {
		s.insert(x);
	}
	void upd(const func &a) {
		st += a.st;
		for (const auto &i : a.s)
			s.insert(i);
		s.erase(prev(s.end()));
	}
	void shift(ll x) {
		st += x;
		vector<ll> v;
		if (s.size()) v.push_back(*prev(s.end())), s.erase(prev(s.end()));
		if (s.size()) v.push_back(*prev(s.end())), s.erase(prev(s.end()));
		while (v.size()) {
			s.insert(s.end(), v.back() + x);
			v.pop_back();
		}
	}
	void print() {
		cout << "s: ";
		for (const auto &i : s) cout << i << " "; cout << '\n';
		cout << "start: " << st << '\n';
	}
};

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

void dfs(int v, int prev, func &f) {
	int big = -1, sh;
	for (const auto &i : g[v])
		if (i.to != prev && (big == -1 || sz[big] < sz[i.to])) big = i.to, sh = i.w;
	if (big == -1) {
		f = func();
		return;
	}
	dfs(big, v, f);
	f.shift(sh);
	func f2;
	for (const auto &i : g[v]) {
		if (i.to != prev && i.to != big) {
			f2.clear();
			dfs(i.to, v, f2);
			f2.shift(i.w);
			f.upd(f2);
		}
	}
	if (OO) {
		cout << "finishing node " << v << '\n';
		f.print();
		cout << '\n';
	}
}

int dfs(int v = 0, int prev = 0) {
	sz[v] = 1;
	for (const auto &i : g[v])
		if (i.to != prev)
			sz[v] += dfs(i.to, v);
	return sz[v];
}

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));
	}
	sz.resize(n);
	dfs();
	func f;
	dfs(0, 0, f);
	ll ans = f.st;
	ll pos = 0;
	ll slope = (ll)f.s.size() - 1;
	auto it = f.s.begin();
	while (slope > 0) {
		ans -= slope * (*it - pos);
		pos = *it;
		slope--;
		it++;
	}
	finish(ans);
}

Compilation message

fireworks.cpp: In member function 'void func::print()':
fireworks.cpp:54:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : s) cout << i << " "; cout << '\n';
   ^~~
fireworks.cpp:54:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : s) cout << i << " "; cout << '\n';
                                             ^~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -