Submission #469830

#	Time	Username	Problem	Language	Result	Execution time	Memory
469830		jwvg0425	Fireworks (APIO16_fireworks)	C++17	100 / 100	279 ms	106184 KiB

fireworks

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

vector<ii64> edge[300005];

struct Data
{
	pq<i64> lside;
	pq<i64, greater<i64>> rside;
	i64 val = 0;

	void apply(i64 len)
	{
		if (lside.empty())
		{
			lside.push(len);
			rside.push(len);
			return;
		}

		auto x = lside.top();
		lside.pop();
		lside.push(x + len);
		auto pt = rside.top();
		rside = pq<i64, greater<i64>>();
		rside.push(pt + len);
	}

	void merge(Data& r)
	{
		if (lside.empty())
		{
			swap(lside, r.lside);
			swap(rside, r.rside);
			val = r.val;
			return;
		}

		val += r.val;

		while (!r.lside.empty())
		{
			auto t = r.lside.top();
			r.lside.pop();

			if (rside.top() > t)
			{
				lside.push(t);
				continue;
			}

			auto pt = rside.top();
			val += t - pt;
			lside.push(pt);

			rside.pop();
			rside.push(t);
		}

		while (!r.rside.empty())
		{
			auto t = r.rside.top();
			r.rside.pop();

			if (lside.top() < t)
			{
				rside.push(t);
				continue;
			}

			auto pt = lside.top();
			val += pt - t;
			rside.push(pt);

			lside.pop();
			lside.push(t);
		}
	}
};

Data dfs(int root)
{
	Data result;

	for (auto& [e, c] : edge[root])
	{
		auto x = dfs(e);
		x.apply(c);

		result.merge(x);
	}

	return result;
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i = 2; i <= n + m; i++)
	{
		i64 p, c;
		scanf("%lld %lld", &p, &c);

		edge[p].emplace_back(i, c);
	}

	printf("%lld\n", dfs(1).val);

	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |   scanf("%lld %lld", &p, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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