Submission #78215

#	Time	Username	Problem	Language	Result	Execution time	Memory
78215		qkxwsm	Fireworks (APIO16_fireworks)	C++14	100 / 100	315 ms	142088 KiB

fireworks

/*
    _____
  .'     '.
 /  0   0  \
|     ^     |
|  \     /  |
 \  '---'  /
  '._____.'
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

struct chash
{
	int operator()(int x) const
	{
		x ^= (x >> 20) ^ (x >> 12);
		return x ^ (x >> 7) ^ (x >> 4);
	}
};

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using hashtable = gp_hash_table<T, U, chash>;
random_device(rd);
mt19937 rng(rd());

template<class T>
void readi(T &x)
{
	T input = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		input = input * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		input = -input;
	}
	x = input;
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int aout[20];
	int ilen = 0;
	while(output)
	{
		aout[ilen] = ((output % 10));
		output /= 10;
		ilen++;
	}
	for (int i = ilen - 1; i >= 0; i--)
	{
		putchar(aout[i] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
template<class T, class U>
T nmod(T &x, U mod)
{
	if (x >= mod) x -= mod;
}
template<class T>
T gcd(T a, T b)
{
	return (b ? gcd(b, a % b) : a);
}
template<class T>
T randomize(T mod)
{
	return (uniform_int_distribution<T>(0, mod - 1))(rng);
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-10;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 300013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;

int N, M;
int parent[MAXN];
ll dup[MAXN];
vector<int> edge[MAXN];
int subtree[MAXN], heavy[MAXN];
ll ans = 0;
priority_queue<ll> pos[MAXN];
int slope[MAXN];
vector<ll> changes;

void debugpq(priority_queue<ll> pq)
{
	vector<ll> vec;
	while(!pq.empty())
	{
		vec.PB(pq.top());
		pq.pop();
	}
	reverse(vec.begin(), vec.end());
	for (ll x : vec)
	{
		cerr << x << ' ';
	}
	cerr << endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	// cout << fixed << setprecision(10);
	// cerr << fixed << setprecision(10);
	// freopen ("file.in", "r", stdin);
	// freopen ("file.out", "w", stdout);
	cin >> N >> M;
	M += N;
	swap(N, M);
	for (int i = 1; i < N; i++)
	{
		cin >> parent[i] >> dup[i];
		parent[i]--;
		edge[parent[i]].PB(i);
	}
	for (int u = N - 1; u >= 0; u--)
	{
		subtree[u] = 1;
		for (int v : edge[u])
		{
			subtree[u] += subtree[v];
		}
		heavy[u] = N;
		for (int v : edge[u])
		{
			if (subtree[v] * 2 >= subtree[u])
			{
				heavy[u] = v;
			}
		}
	}
	// for (int i = 0; i < N; i++)
	// {
	// 	for (int j = 0; j < MAXN; j++)
	// 	{
	// 		dp[i][j] = LLINF;
	// 	}
	// 	if (i >= M) dp[i][0] = 0;
	// }
	// // cerr << M << " nons\n";
	// for (int u = M - 1; u >= 0; u--)
	// {
	// 	for (int i = 0; i < MAXN; i++)
	// 	{
	// 		dp[u][i] = 0;
	// 		for (int v : edge[u])
	// 		{
	// 			ll cost = LLINF;
	// 			for (int j = 0; j <= i; j++)
	// 			{
	// 				ckmin(cost, dp[v][j] + abs(i - (j + dup[v])));
	// 			}
	// 			dp[u][i] += cost;
	// 			if (cost == LLINF)
	// 			{
	// 				dp[u][i] = LLINF;
	// 				break;
	// 			}
	// 		}
	// 	}
	// }
	// ans = LLINF;
	// for (int i = 0; i < MAXN; i++)
	// {
	// 	ckmin(ans, dp[0][i]);
	// }
	for (int i = M; i <= N; i++)
	{
		pos[i].push(0);
		pos[i].push(0);
		slope[i] = -1; //it's the slope BEFORE the first element!
	}
	//when slope is positive, you use all the new guys, otherwise you use the old guys
	for (int u = M - 1; u >= 0; u--)
	{
		// slope[u] = 0;
		// cerr << u << " start " << slope[u] << " has ";
		// debugpq(pos[u]);
		for (int v : edge[u])
		{
			ll d = dup[v];
			//convolve this guy with v
			//let L...R be the region with slope 0
			//then L...L+d is slope -1
			//L+d...R+d is slope 0
			//R+d...INF is slope 1
			//after size = 0, slope = slope[i]
			//after size = -slope[i], slope = 0
			while(pos[v].size() > 1 - slope[v])
			{
				pos[v].pop();
			}
			ll R = pos[v].top();
			pos[v].pop();
			ll L = pos[v].top();
			pos[v].pop();
			// cerr << "vert " << v << ' ' << L << ' ' << R << endl;
			// if (pos[v].empty())
			// {
			// 	pos[v].push(0);
			// 	cerr << "start " << slope[v] << endl;
			// }
			pos[v].push(L + d);
			pos[v].push(R + d);
			// cerr << v << " start " << slope[v] << " has ";
			// debugpq(pos[v]);
			slope[u] += slope[v];
		}
		if (heavy[u] != N)
		{
			swap(pos[u], pos[heavy[u]]);
		}
		for (int v : edge[u])
		{
			//then add this guy
			if (v == heavy[u]) continue;
			// cerr << "send from " << v << " to " << u << endl;
			while(!pos[v].empty())
			{
				ll x = pos[v].top();
				pos[v].pop();
				// cerr << "pos " << u << " push " << x << endl;
				pos[u].push(x);
			}
		}
		// cerr << u << " start " << slope[u] << " has ";
		// debugpq(pos[u]);
	}
	ll curslope = slope[0], cursum = 0;
	while(!pos[0].empty())
	{
		ll x = pos[0].top();
		pos[0].pop();
		changes.PB(x);
	}
	changes.PB(0);
	reverse(changes.begin(), changes.end());
	for (int i = 0; i < changes.size() - 1; i++)
	{
		cursum += (changes[i + 1] - changes[i]) * curslope;
		ckmin(ans, cursum);
		curslope++;
	}
	for (int i = 1; i < N; i++)
	{
		ans += dup[i];
	}
	cout << ans << '\n';
	// cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int32_t main()':
fireworks.cpp:256:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(pos[v].size() > 1 - slope[v])
          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~
fireworks.cpp:305:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < changes.size() - 1; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~

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