Submission #1199333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199333		catch_me_if_you_can	Fireworks (APIO16_fireworks)	C++20	7 / 100	6 ms	14408 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];
int off[MX];//if you see value S, real value is S+off[u].
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};
		off[u] = 0;
		return;
	}
	for(int v: adj[u])
	{
		dfs(v);
		if((dp[u].size() < dp[v].size()))
		{
			swap(dp[u], dp[v]);
			swap(off[u], off[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+off[v]-off[u]);
		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) + off[u]);
		dp[u].erase(it);
	}
	/*cout << "For vertex u " << u << " we have " << endl;
	for(auto s: dp[u])
		cout << (s+off[u]) << " ";
	cout << endl;
	cout << "! = " << T[u][1] << " " << T[u][0] << endl;*/
	auto it = prev(dp[u].end());
	int D = *it;
	dp[u].erase(it);
	T[u][1]--;
	T[u][0]+=(D + off[u]);
	dp[u].insert(D+w[u]-off[u]);
	T[u][1]++;
	T[u][0]-=(D+w[u]);
	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: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45