Submission #111405

#	Time	Username	Problem	Language	Result	Execution time	Memory
111405		diamond_duke	Fireworks (APIO16_fireworks)	C++11	100 / 100	464 ms	19372 KiB

fireworks

#include <algorithm>
#include <cstdio>
using ll = long long;
int lson[1200005], rson[1200005], t_cnt;
ll val[1200005];
int merge(int u, int v)
{
	if (!u || !v)
		return u | v;
	if (val[u] < val[v])
		std::swap(u, v);
	rson[u] = merge(rson[u], v);
	std::swap(lson[u], rson[u]);
	return u;
}
inline int new_node(ll x) { val[++t_cnt] = x; return t_cnt; }
void pop(int &u) { u = merge(lson[u], rson[u]); }
int fa[600005], faw[600005], deg[600005], rt[600005];
int main()
{
	// freopen("uoj-205.in", "r", stdin);
	int n, m;
	scanf("%d%d", &n, &m);
	ll ans = 0;
	for (int i = 1; i < n + m; i++)
	{
		scanf("%d%d", fa + i, faw + i);
		deg[--fa[i]]++;
		ans += faw[i];
	}
	for (int u = n + m - 1; u; u--)
	{
		ll l = 0, r = 0;
		if (u < n)
		{
			while (--deg[u])
				pop(rt[u]);
			r = val[rt[u]];
			pop(rt[u]);
			l = val[rt[u]];
			pop(rt[u]);
		}
		rt[u] = merge(rt[u], merge(new_node(l + faw[u]), new_node(r + faw[u])));
		rt[fa[u]] = merge(rt[fa[u]], rt[u]);
	}
	while (deg[0]--)
		pop(rt[0]);
	while (rt[0])
	{
		ans -= val[rt[0]];
		pop(rt[0]);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:23: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:27: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: 45 / 45