제출 #1199390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199390		catch_me_if_you_can	Fireworks (APIO16_fireworks)	C++20	55 / 100	99 ms	26300 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e5+5;
const int INF = 1e17;

vector<int> adj[MX];
int w[MX];

multiset<int> dp[MX];
in T[MX];//final function is TRUE T[u][1]*X + T[u][0].

void dfs(int u)
{
	if(adj[u].empty())
	{
		dp[u].insert(w[u]);
		dp[u].insert(w[u]);
		T[u] = {-w[u], 1};
		return;
	}
	for(int v: adj[u])
	{
		dfs(v);
		if((dp[u].size() < dp[v].size()))
		{
			swap(dp[u], dp[v]);
			swap(T[u], T[v]);
		}
		T[u][0]+=T[v][0];
		T[u][1]+=T[v][1];
		for(int X: dp[v])
			dp[u].insert(X);
		dp[v].clear();
	}
	if(u == 1)
		return;
	while(T[u][1] > 1)
	{
		auto it = prev(dp[u].end());
		T[u][1]--;
		T[u][0]+=(*it);
		dp[u].erase(it);
	}
	vector<int> V;
	T[u][0]-=w[u];
	while(T[u][1] >= 0)
	{
		T[u][1]--;
		auto it = prev(dp[u].end());
		V.pb((*it) + w[u]);
		dp[u].erase(it);
	}
	for(auto s: V)
	{
		dp[u].insert(s);
		T[u][1]++;
	}
	return;
}

signed main()
{
	fast();
	int n, m; cin >> n >> m; n+=m;
	for(int i = 2; i <= n; i++)
	{
		int s; cin >> s >> w[i];
		adj[s].pb(i);
	}
	dfs(1);
	int ans = T[1][0];
	while(T[1][1]--)
	{
		auto it = prev(dp[1].end());
		ans+=(*it);
		dp[1].erase(it);
	}
	cout << ans << "\n";
	return 0;
}	

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