Submission #512313

#	Time	Username	Problem	Language	Result	Execution time	Memory
512313		rk42745417	Fireworks (APIO16_fireworks)	C++17	0 / 100	1 ms	204 KiB

fireworks

/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "\e[1;31m" << #x << " = " << (x) << "\e[0m\n"
#define print(x) emilia_mata_tenshi(#x, begin(x), end(x))
template<typename T> void emilia_mata_tenshi(const char *s, T l, T r) {
	cerr << "\e[1;33m" << s << " = [";
	while(l != r) {
		cerr << *l;
		cerr << (++l == r ? ']' : ',');
	}
	cerr << "\e[0m\n";
}

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-7;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
static int Lamy_is_cute = []() {
	EmiliaMyWife
	return 48763;
}();
/*--------------------------------------------------------------------------------------*/

struct dat {
	priority_queue<ll> slope;
	ll l = 0, r = 0;
	ll zero_ans = 0;
	int zero_slope = 0;
	inline int size() { return slope.size(); }
	void shift(int c) {
		while(slope.size() > zero_slope)
			slope.pop();
		if(zero_slope == 0) {
			zero_slope++;
		}
		else
			slope.pop();
		l += c, r += c;
		slope.push(l);
		slope.push(r);
		zero_ans += c;
	}
	void update() {
		while(slope.size() > zero_slope + 1)
			slope.pop();
		ll a = slope.top(); slope.pop();
		l = slope.top();
		r = a;
		slope.push(a);
	}
	void merge(dat b) {
		while(!b.slope.empty()) {
			slope.push(b.slope.top());
			b.slope.pop();
		}
		zero_ans += b.zero_ans;
		zero_slope += b.zero_slope;
		update();
	}
};

signed main() {
	int n, m;
	cin >> n >> m;
	n += m;
	vector<vector<pair<int, int>>> edge(n + 1);
	for(int i = 2; i <= n; i++) {
		int p, c;
		cin >> p >> c;
		edge[p].push_back({i, c});
	}
	vector<dat> arr(n + 1);
	function<void(int)> dfs = [&](int u) {
		for(const auto &[v, c] : edge[u]) {
			dfs(v);
			arr[v].shift(c);
			if(arr[u].slope.empty()) {
				swap(arr[u], arr[v]);
				continue;
			}
			if(arr[v].size() > arr[u].size())
				swap(arr[u], arr[v]);
			arr[u].merge(arr[v]);
		}

		/* debug
		debug(u);
		ll cur = arr[u].zero_ans, sl = -arr[u].zero_slope;
		vector<ll> ch;
		while(!arr[u].slope.empty()) {
			ch.push_back(arr[u].slope.top());
			arr[u].slope.pop();
		}
		for(ll a : ch)
			arr[u].slope.push(a);
		reverse(ch.begin(), ch.end());
		ll prv = 0;
		print(ch);
		debug(cur);
		debug(sl);
		for(ll a : ch) {
			cur += (a - prv) * sl;
			sl++;
			cerr << a << ' ' << cur << '\n';
			if(sl == 0)
				break;
			prv = a;
		}
		cerr << "-------------------\n";
		*/
	};
	dfs(1);
	ll cur = arr[1].zero_ans, sl = -arr[1].zero_slope;
	vector<ll> ch;
	while(!arr[1].slope.empty()) {
		ch.push_back(arr[1].slope.top());
		arr[1].slope.pop();
	}
	reverse(ch.begin(), ch.end());
	ll prv = 0;
	/* debug
	print(ch);
	debug(cur);
	debug(sl);
	*/
	for(ll a : ch) {
		cur += (a - prv) * sl;
		sl++;
		//cerr << a << ' ' << cur << '\n';
		if(sl == 0)
			break;
		prv = a;
	}
	cout << cur << '\n';
}

Compilation message (stderr)

fireworks.cpp: In member function 'void dat::shift(int)':
fireworks.cpp:47:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |   while(slope.size() > zero_slope)
      |         ~~~~~~~~~~~~~^~~~~~~~~~~~
fireworks.cpp: In member function 'void dat::update()':
fireworks.cpp:60:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |   while(slope.size() > zero_slope + 1)
      |         ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45