Submission #256861

#	Time	Username	Problem	Language	Result	Execution time	Memory
256861		Goolakh	Fireworks (APIO16_fireworks)	C++17	100 / 100	241 ms	66296 KiB

fireworks

// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=3e5+10, maxm=5e4+10, lg=21, mod=998244353, inf=1e18;

#define pq priority_queue<ll>

ll n,m,w[maxn],rr;
vector<ll> g[maxn];

pq dff(ll v=0){
	pq q;
	if(v<n){
		for(auto u:g[v]){
			pq p=dff(u);
			if(SZ(q)<SZ(p)) swap(p,q);
			while(!p.empty()) q.push(p.top()), p.pop();
		}
		for(int i=1;i<SZ(g[v]);i++) q.pop();
		ll x=q.top()+w[v]; q.pop();
		ll y=q.top()+w[v]; q.pop();
		q.push(x), q.push(y);
	}
	else q.push(w[v]), q.push(w[v]);
	return q;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	for(int i=1,x;i<n+m;i++){
		cin>>x>>w[i]; rr+=w[i];
		g[--x].pb(i);
	}
	pq q=dff();
	ll p=q.top(); q.pop();
	ll tt=0;
	while(!q.empty()) rr-=tt++*(p-q.top()), p=q.top(), q.pop();
	cout<<rr-tt*p;
	
	return 0;
}



 

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