Submission #652852

#	Time	Username	Problem	Language	Result	Execution time	Memory
652852		lovrot	Fireworks (APIO16_fireworks)	C++17	100 / 100	255 ms	95672 KiB

fireworks

#include <bits/stdc++.h>

#define X first
#define Y second
#define pb push_back 

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

struct func{
	ll a;
	ll b;
	int ind;
};

const int N = 300010;

int n, m, siz[N];
ll edge[N];

vector<int> g[N];
priority_queue<ll> slope[N];

func merge(func a, func b){
	func ret;
	ret.a = a.a + b.a;
	ret.b = a.b + b.b;	
	ret.ind = a.ind;
	
	while(!slope[b.ind].empty()){ 
		slope[a.ind].push(slope[b.ind].top()); 
		slope[b.ind].pop();
	}
	return ret;
}

func f(int u){
	func ret;
	if(g[u].empty()){
		ret.a = 1;
		ret.b = -edge[u];
		ret.ind = u;
		slope[u].push(edge[u]);
		slope[u].push(edge[u]);
		return ret;
	} 
	ret = f(g[u][0]);
	int ind = ret.ind;
	for(int i = 1; i < g[u].size(); i++){
		ret = merge(ret, f(g[u][i]));
	}
	while(ret.a > 1){
		ll val = slope[ind].top();
		slope[ind].pop();
		ret.a--;
		ret.b += val;
	}
	ll val = slope[ind].top() + edge[u];
	slope[ind].pop(); 
	ll val2 = slope[ind].top() + edge[u];
	slope[ind].pop(); 
	slope[ind].push(val);
	slope[ind].push(val2);
	ret.b -= edge[u];
	return ret;
}

int dfs(int u){
	int ret = 1;
	for(int v : g[u]){
		ret += dfs(v);
	}
	siz[u] = ret;
	return ret;
}

int main(){
	scanf("%d%d\n", &n, &m);
	
	for(int i = 2; i <= n + m; i++){
		int par;
		ll val;
		scanf("%d%lld", &par, &val);
		g[par].pb(i);
		edge[i] = val;
	}
	
	dfs(1);
	
	for(int i = 1; i <= n; i++){
		sort(g[i].begin(), g[i].end(), [](int a, int b) -> bool {return (siz[a] > siz[b]) || (siz[a] == siz[b] && a < b);});	
	}
	
	func res = f(1);
	ll ans = slope[res.ind].top() + res.b;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'func f(int)':
fireworks.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i = 1; i < g[u].size(); i++){
      |                 ~~^~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%d\n", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
fireworks.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d%lld", &par, &val);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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