Submission #386018

#	Time	Username	Problem	Language	Result	Execution time	Memory
386018		grt	Fireworks (APIO16_fireworks)	C++17	7 / 100	11 ms	14444 KiB

fireworks

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 300 * 1000 + 10;
const ll INF = 1e18;
int n, m;
int p[nax], v[nax];
int in[nax];
queue<int>Q;
bool leaf[nax];
pair<ll,ll> f[nax], d[nax];
multiset<ll>S[nax];

int main() {
	cin >> n >> m;
	for(int i = n; i < n + m; ++i) leaf[i] = true;
	n += m;
	for(int i = 1; i < n; ++i) {
		cin >> p[i] >> v[i];
		p[i]--;
		in[p[i]]++;
	}
	for(int i = 0; i < n; ++i) {
		if(in[i] == 0) {
			Q.push(i);
		}
	}
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		//~ if(x == 0) break;
		if(leaf[x]) {
			d[x] = {v[x], v[x]};
			f[x] = {1, -v[x]};
		}
			while(f[x].ST > 1) {
				auto it = S[x].end();
				it--;
				f[x].ST--;
				f[x].ND += (*it);
				S[x].erase(it);
			}
			if((int)S[x].size() > 0) {
			auto it = S[x].end();
			it--;
			d[x].ND = (*it);
			it--;
			d[x].ST = (*it);
			S[x].clear();
			d[x].ST += v[x];
			d[x].ND += v[x];
			f[x].ND -= v[x];
		}
		//~ cout << x << ": " << d[x].ST << " " << d[x].ND << "\n";
		if(x == 0) break;
		in[p[x]]--;
		S[p[x]].insert(d[x].ST);
		S[p[x]].insert(d[x].ND);
		f[p[x]].ST += f[x].ST;
		f[p[x]].ND += f[x].ND;
		if(in[p[x]] == 0) {
			Q.push(p[x]);
		}
	}
	// -2 3
	//~ cout << f[0].ST << " " << f[0].ND << "\n";
	cout << f[0].ND + d[0].ND;
}

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