Submission #668527

#	Time	Username	Problem	Language	Result	Execution time	Memory
668527		QwertyPi	Fireworks (APIO16_fireworks)	C++14	0 / 100	35 ms	52948 KiB

fireworks

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

const int MAXN = 300011;
int p[MAXN], c[MAXN];
pair<int, int> dp[MAXN];
vector<int> G[MAXN];
int cost[MAXN], w[MAXN];
int ans = 0;

struct Firework{
	Firework() = default;
	Firework(int c){
		c0 = c, n = 1;
		v = multiset<int>{c, c};
	}
	int c0 = 0, n = 0;
	multiset<int> v;
} fireworks[MAXN];

void operator+= (Firework& a, Firework& b){
	a.c0 += b.c0; a.n += b.n;
	for(auto i : b.v) a.v.insert(i);
	b.v.clear();
}

void operator+= (Firework& a, int c){
	a.c0 += c;
	int l1 = *--a.v.end(); a.v.erase(--a.v.end());
	int l2 = *--a.v.end(); a.v.erase(--a.v.end());
	a.v.insert(l1 + c); a.v.insert(l2 + c);
}

void f(Firework& a){
	while(a.v.size() > a.n + 1){
		a.v.erase(--a.v.end());
	}
}

int rt[MAXN];
int dfs1(int v){
	vector<int> sons;
	for(auto i : G[v]){
		dfs1(i);
		sons.push_back(i);
	}

	if(sons.size() == 0){
		rt[v] = v;
		fireworks[v] = Firework(0);
	}else{
		for(auto u : sons){
			fireworks[rt[u]] += c[u];
		}
		for(int i = 1; i < sons.size(); i++){
			if(fireworks[rt[sons[i]]].n > fireworks[rt[sons[0]]].n){
				swap(sons[0], sons[i]);
			}
		}
		for(int i = 1; i < sons.size(); i++){
			fireworks[rt[sons[0]]] += fireworks[rt[sons[i]]];
		}
		rt[v] = rt[sons[0]];
		f(fireworks[rt[v]]);
	}
}

int32_t main() {
	int n, m;
	cin >> n >> m;
	for(int i = 2; i <= n + m; i++){
		cin >> p[i] >> c[i];
		G[p[i]].push_back(i);
	}

	dfs1(1);
	int ans = fireworks[rt[1]].c0, idx = 0, dx = -fireworks[rt[1]].n;
	for(auto i : fireworks[rt[1]].v){
		ans += dx * (i - idx); idx = i; dx++;
	}
	cout << ans << endl;
}

Compilation message (stderr)

fireworks.cpp: In function 'void f(Firework&)':
fireworks.cpp:38:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |  while(a.v.size() > a.n + 1){
      |        ~~~~~~~~~~~^~~~~~~~~
fireworks.cpp: In function 'long long int dfs1(long long int)':
fireworks.cpp:58:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i = 1; i < sons.size(); i++){
      |                  ~~^~~~~~~~~~~~~
fireworks.cpp:63:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 1; i < sons.size(); i++){
      |                  ~~^~~~~~~~~~~~~
fireworks.cpp:69:1: warning: no return statement in function returning non-void [-Wreturn-type]
   69 | }
      | ^

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