Submission #111404

#	Time	Username	Problem	Language	Result	Execution time	Memory
111404		diamond_duke	Fireworks (APIO16_fireworks)	C++11	55 / 100	789 ms	16664 KiB

fireworks

#include <algorithm>
#include <cstdio>
#include <vector>
using ll = long long;
struct segment
{
	ll x, y, k;
	segment(ll a, ll b, ll c) : x(a), y(b), k(c) {}
};
int fa[100005], faw[100005], idx[100005];
std::vector<int> son[100005];
std::vector<segment> dp[100005];
std::pair<ll, int> seq[100005];
int main()
{
	// freopen("uoj-205.in", "r", stdin);
	int n, m;
	scanf("%d%d", &n, &m);
	n += m;
	for (int i = 1; i < n; i++)
	{
		scanf("%d%d", fa + i, faw + i);
		son[--fa[i]].push_back(i);
	}
	for (int u = n - 1; u >= 0; u--)
	{
		if (son[u].empty())
		{
			dp[u] = {{0, faw[u], -1}, {faw[u], 0, 1}};
			continue;
		}
		int cnt = 0;
		ll x_sum = 0, y_sum = 0, k_sum = 0;
		for (int v : son[u])
		{
			for (int i = 0; i < dp[v].size(); i++)
				seq[cnt++] = {dp[v][i].x, v};
			y_sum += dp[v][0].y;
			idx[v] = -1;
		}
		std::sort(seq, seq + cnt);
		dp[u] = {{0, y_sum, 0}};
		for (int i = 0; i < cnt; i++)
		{
			if (seq[i].first > x_sum)
			{
				dp[u].back().k = k_sum;
				y_sum += k_sum * (seq[i].first - x_sum);
				dp[u].emplace_back(seq[i].first, y_sum, 0);
				x_sum = seq[i].first;
			}
			int v = seq[i].second;
			k_sum += dp[v][idx[v] + 1].k - (~idx[v] ? dp[v][idx[v]].k : 0);
			idx[v]++;
		}
		dp[u].back().k = k_sum;
		for (int v : son[u])
		{
			dp[v].clear();
			dp[v].shrink_to_fit();
		}
		if (!u)
			break;
		for (int i = 0; i < dp[u].size(); i++)
		{
			dp[u][i].y += dp[u][i].x;
			dp[u][i].k++;
			if (dp[u][i].k < 0)
				continue;
			int j = dp[u].size();
			dp[u].push_back(dp[u].back());
			while (j > i)
			{
				dp[u][j] = dp[u][j - 1];
				if (j > i + 1)
				{
					dp[u][j].y += dp[u][j].x;
					dp[u][j].k++;
				}
				dp[u][j].x += faw[u];
				j--;
			}
			dp[u][i].k = 0;
			break;
		}
		for (int i = 0; i < dp[u].size(); i++)
		{
			dp[u][i].y += faw[u] - dp[u][i].x * 2;
			dp[u][i].k -= 2;
			if (dp[u][i].k < 0)
				continue;
			while (dp[u].size() > i + 1)
				dp[u].pop_back();
			dp[u][i].k = 0;
			while (i >= 0)
			{
				dp[u][i].y += dp[u][i].x;
				dp[u][i].k++;
				i--;
			}
			break;
		}
	}
	for (auto &it : dp[0])
	{
		if (it.k >= 0)
		{
			printf("%lld\n", it.y);
			return 0;
		}
	}
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:36:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < dp[v].size(); i++)
                    ~~^~~~~~~~~~~~~~
fireworks.cpp:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < dp[u].size(); i++)
                   ~~^~~~~~~~~~~~~~
fireworks.cpp:86:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < dp[u].size(); i++)
                   ~~^~~~~~~~~~~~~~
fireworks.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (dp[u].size() > i + 1)
           ~~~~~~~~~~~~~^~~~~~~
fireworks.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", fa + i, faw + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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