Submission #162822

#	Time	Username	Problem	Language	Result	Execution time	Memory
162822		HungAnhGoldIBO2020	Fireworks (APIO16_fireworks)	C++14	100 / 100	241 ms	53376 KiB

fireworks

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+2;
int par[N],c[N];
struct slopetrick{
	int a,b;
	priority_queue<int> *lis;
	slopetrick operator+(slopetrick x){
		slopetrick ans;
		ans.a = a + x.a;
		ans.b = b + x.b;
		if(x.lis->size()<lis->size()){
			ans.lis=lis;
			while(x.lis->size()){
				ans.lis->push(x.lis->top());
				x.lis->pop();
			}
		}
		else{
			ans.lis=x.lis;
			while(lis->size()){
				ans.lis->push(lis->top());
				lis->pop();
			}
		}
		return ans;
	}
} data[N];
signed main(){
//	freopen("text.txt","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,i,j,k,l;
	cin>>n>>m;
	for(i=2;i<=n+m;i++){
		cin>>par[i]>>c[i];
	}
	for(i=1;i<=n+m;i++){
		data[i].a=0;
		data[i].b=0;
		data[i].lis=new priority_queue<int>;
	}
	for(i=n+m;i>n;i--){
		data[i].a=1;
		data[i].b=-c[i];
		//cout<<i<<endl;
		data[i].lis->push(c[i]);
		data[i].lis->push(c[i]);
		//cout<<i<<endl;
		data[par[i]] = data[par[i]] + data[i];
	}
	for(i=n;i>1;i--){
		while(data[i].a>1){
			j=data[i].lis->top();
			data[i].lis->pop();
			data[i].a--;
			data[i].b+=j;
		}
		j=data[i].lis->top();
		data[i].lis->pop();
		k=data[i].lis->top();
		data[i].lis->pop();
		j+=c[i];
		k+=c[i];
		data[i].b-=c[i];
		data[i].lis->push(k);
		data[i].lis->push(j);
		data[par[i]] = data[par[i]] + data[i];
	}
	while(data[1].a>0){
		j=data[1].lis->top();
		data[1].lis->pop();
		data[1].a--;
		data[1].b+=j;
	}
	cout<<data[1].b;
}
/*
4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3
*/

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:34:16: warning: unused variable 'l' [-Wunused-variable]
  int n,m,i,j,k,l;
                ^

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