Submission #244918

#	Time	Username	Problem	Language	Result	Execution time	Memory
244918		Red_Inside	Fireworks (APIO16_fireworks)	C++17	100 / 100	584 ms	70904 KiB

fireworks

#include <bits/stdc++.h>
#include <random>

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
//tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define	IOS ios_base::sync_with_stdio(0);
#define en "\n"
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define sortv(vv) sort(vv.begin(), vv.end())
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
const ll maxn=3e5+100,inf=1e9,LOG=23,mod=1e9+7;
ll block = 500, timer = 0;
const ld EPS = 1e-7;

#define bt(i) (1 << (i))
#define int ll
#define y1 yy
//#define double long double
#define pii pair <int, int>

int n, m, a[maxn], b[maxn], c[maxn];
multiset <int> st[maxn];
vector <int> edge[maxn];

void dfs(int v)
{
	if(edge[v].size() == 0)
	{
		st[v].insert(c[v]);
		st[v].insert(c[v]);
		a[v] = 1;
		b[v] = -c[v];
		/*cout << "V " << v << "  - ";
		for(auto i : st[v])
		{
			cout << i << " ";
		}
		cout << "  " << a[v] << " " << b[v] << endl;*/
		return;
	}
	for(auto to : edge[v])
	{
		dfs(to);
		if(st[to].size() > st[v].size()) swap(st[v], st[to]);
		while(st[to].size())
		{
			st[v].insert(*st[to].begin());
			st[to].erase(st[to].begin());
		}
		a[v] += a[to];
		b[v] += b[to];
	}
	while(a[v] > 1)
	{
		auto it = st[v].end();
		it--;
		b[v] += *it;
		st[v].erase(it);
		a[v]--;
	}
	auto it = st[v].end();
	it--;
	int c1 = *it;
	it--;
	int c2 = *it;
	st[v].erase(st[v].find(c1));
	st[v].insert(c1 + c[v]);
	st[v].erase(st[v].find(c2));
	st[v].insert(c2 + c[v]);
	b[v] -= c[v];
	/*cout << "V " << v << "  - ";
	for(auto i : st[v])
	{
		cout << i << " ";
	}
	cout << "  " << a[v] << " " << b[v] << endl;*/
}

main()
{
	IOS
	cin >> n >> m;
	n += m;
	forn(2, i, n)
	{
		int p;
		cin >> p >> c[i];
		edge[p].pb(i);
	}
	dfs(1);
	while(a[1] > 0)
	{
		auto it = st[1].end();
		it--;
		a[1]--;
		b[1] += *it;
		st[1].erase(it);
	}
	cout << b[1] + a[1] * (st[1].size() ? (*st[1].rbegin()) : 0);
}

Compilation message (stderr)

fireworks.cpp:9:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
fireworks.cpp:99:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

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