Submission #652850

#	Time	Username	Problem	Language	Result	Execution time	Memory
652850		lovrot	Fireworks (APIO16_fireworks)	C++17	19 / 100	27 ms	43236 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];
multiset<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;
	
	for(auto x : slope[b.ind]) slope[a.ind].insert(x); 
	return ret;
}

func f(int u){
	func ret;
	if(g[u].empty()){
		ret.a = 1;
		ret.b = -edge[u];
		ret.ind = u;
		slope[u].insert(edge[u]);
		slope[u].insert(edge[u]);
		return ret;
	} 
	ret = f(g[u][0]);
	for(int i = 1; i < g[u].size(); i++){
		ret = merge(ret, f(g[u][i]));
	}
	int ind = ret.ind;
	while(ret.a > 1){
		ll last = *slope[ind].rbegin();
		slope[ind].erase(prev(slope[ind].end()));
		ret.b += last;
		ret.a--;
	}
	ll val = *prev(slope[ind].end()) + edge[u];
	slope[ind].erase(prev(slope[ind].end())); 
	ll val2 = *prev(slope[ind].end()) + edge[u];
	slope[ind].erase(prev(slope[ind].end())); 
	ret.b -= edge[u];
	slope[ind].insert(val);
	slope[ind].insert(val2);
	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, val;
		scanf("%d%d", &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];});	
	}
	
	func res = f(1);
	ll ans = *slope[res.ind].rbegin() + res.b;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

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

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