Submission #676541

#	Time	Username	Problem	Language	Result	Execution time	Memory
676541		numberes	Fireworks (APIO16_fireworks)	C++17	100 / 100	253 ms	92016 KiB

fireworks

/**
 * @date    2022-12-31 15:25:48
 * @author  numberes
 * 煮不在乎.RAmen!
 * https://oj.uz/problem/view/APIO16_fireworks
 */
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define ll long long
using namespace std;
priority_queue<ll> pq[300005];
ll a[300005],b[300005];
int n,m;
vector<pii> g[300005];
void dfs(int u,int c){
	if(!g[u].size()){
		pq[u].push(c);pq[u].push(c);
		a[u]=1;b[u]=-c;
		return;
	}
	for(auto now:g[u]){
		int v=now.fi,vc=now.se;
		dfs(v,vc);
		if(pq[u].size()<pq[v].size()) swap(pq[u],pq[v]);
		while(!pq[v].empty()){pq[u].push(pq[v].top());pq[v].pop();}
		a[u]+=a[v];b[u]+=b[v];
	}
	while(a[u]>1){
		a[u]--;b[u]+=pq[u].top();
		pq[u].pop();
	}
	int k=a[u];vector<ll> upd;
	while(k>=0){
		upd.pb(pq[u].top()+c);
		pq[u].pop();
		k--;
	}
	for(auto now:upd) pq[u].push(now);
	b[u]-=c;
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=2;i<=n+m;i++){
		int u,c;
		scanf("%d %d",&u,&c);
		g[u].pb(mp(i,c));
	}
	dfs(1,0);
	while(a[1]>0){
		a[1]--;b[1]+=pq[1].top();
		pq[1].pop();
	}
	printf("%lld\n",b[1]);
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
fireworks.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d %d",&u,&c);
      |   ~~~~~^~~~~~~~~~~~~~~

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