Submission #474149

#	Time	Username	Problem	Language	Result	Execution time	Memory
474149		CSQ31	Fireworks (APIO16_fireworks)	C++17	100 / 100	398 ms	103492 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (int)(a.size())
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
struct slope{
	multiset<ll>s;
	ll m=0,c=0;
	slope(){}
	slope(ll _m,ll _c ,ll x){
		m = _m;
		c = _c;
		s.insert(x);
		s.insert(x);
	}
	void merge(const slope &t){
		m+=t.m;
		c+=t.c;
		for(ll z:t.s)s.insert(z);
	}
	void upd(ll k){
		while(m>1){
			auto it = s.end();
			it--;
			m--;
			c+=*it;
			s.erase(it);
		}
		auto it = s.end();
		it--;
		ll a = *it+k;
		s.erase(it);
		it = s.end();
		it--;
		ll b = *it+k;
		s.erase(it);
		s.insert(a);s.insert(b);
		c-=k;
	}
};
const int MAXN = 3e5+1;
vii adj(MAXN);
vector<ll>w(MAXN);
vector<slope>dp(MAXN);
void dfs(int v){
	if(!sz(adj[v]))dp[v] = slope(1,-w[v],w[v]);
	for(int x:adj[v]){
		   dfs(x);
		   if(sz(adj[x]))dp[x].upd(w[x]);
	}
	for(int x:adj[v]){
		if(sz(dp[x].s) > sz(dp[v].s)){
			swap(dp[x].s,dp[v].s);
			swap(dp[x].c,dp[v].c);
			swap(dp[x].m,dp[v].m);
		}
		dp[v].merge(dp[x]);
	}
	/*
	cout<<"node"<<" "<<v<<'\n';
	cout<<"container :"<<'\n';
	for(int x:dp[v].s)cout<<x<<" ";
	cout<<'\n';
	cout<<dp[v].m<<" "<<dp[v].c<<'\n';
	* */
	
}
int main()
{
	owo
	int n,m;
	cin>>n>>m;
	for(int i=2;i<=n+m;i++){
		int p;
		cin>>p>>w[i];
		adj[p].pb(i);
	}
	dfs(1);
	while(dp[1].m >= 1){
		auto it = dp[1].s.end();
		it--;
		dp[1].m--;
		dp[1].c+=*it;
		dp[1].s.erase(it);	
	}
	cout<<dp[1].c<<'\n';
}

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