oj.uz

Submission #111403

# Submission time Handle Problem Language Result Execution time Memory
111403 2019-05-15T06:51:56 Z diamond_duke Fireworks (APIO16_fireworks) C++11
26 / 100
 8 ms 5120 KB 
#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<int, 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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4980 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 7 ms 4992 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 7 ms 5120 KB Output is correct
13 Correct 6 ms 5064 KB Output is correct
14 Correct 7 ms 5120 KB Output is correct
15 Correct 6 ms 4992 KB Output is correct
16 Correct 5 ms 5120 KB Output is correct
17 Correct 8 ms 5120 KB Output is correct
18 Correct 5 ms 4992 KB Output is correct
19 Correct 6 ms 5120 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 6 ms 4992 KB Output is correct
12 Correct 6 ms 4980 KB Output is correct
13 Correct 7 ms 4992 KB Output is correct
14 Correct 6 ms 4992 KB Output is correct
15 Correct 8 ms 4992 KB Output is correct
16 Correct 6 ms 4992 KB Output is correct
17 Correct 6 ms 4992 KB Output is correct
18 Correct 7 ms 4992 KB Output is correct
19 Correct 6 ms 4992 KB Output is correct
20 Correct 6 ms 4992 KB Output is correct
21 Correct 7 ms 4992 KB Output is correct
22 Correct 7 ms 5120 KB Output is correct
23 Correct 6 ms 5064 KB Output is correct
24 Correct 7 ms 5120 KB Output is correct
25 Correct 6 ms 4992 KB Output is correct
26 Correct 5 ms 5120 KB Output is correct
27 Correct 8 ms 5120 KB Output is correct
28 Correct 5 ms 4992 KB Output is correct
29 Correct 6 ms 5120 KB Output is correct
30 Incorrect 6 ms 5120 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 6 ms 4992 KB Output is correct
12 Correct 6 ms 4980 KB Output is correct
13 Correct 7 ms 4992 KB Output is correct
14 Correct 6 ms 4992 KB Output is correct
15 Correct 8 ms 4992 KB Output is correct
16 Correct 6 ms 4992 KB Output is correct
17 Correct 6 ms 4992 KB Output is correct
18 Correct 7 ms 4992 KB Output is correct
19 Correct 6 ms 4992 KB Output is correct
20 Correct 6 ms 4992 KB Output is correct
21 Correct 7 ms 4992 KB Output is correct
22 Correct 7 ms 5120 KB Output is correct
23 Correct 6 ms 5064 KB Output is correct
24 Correct 7 ms 5120 KB Output is correct
25 Correct 6 ms 4992 KB Output is correct
26 Correct 5 ms 5120 KB Output is correct
27 Correct 8 ms 5120 KB Output is correct
28 Correct 5 ms 4992 KB Output is correct
29 Correct 6 ms 5120 KB Output is correct
30 Incorrect 6 ms 5120 KB Output isn't correct
31 Halted 0 ms 0 KB -