Submission #991984

#	Time	Username	Problem	Language	Result	Execution time	Memory
991984		kshitij_sodani	Fireworks (APIO16_fireworks)	C++17	26 / 100	20 ms	36188 KiB

fireworks

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

#define a first
#define b second
#define pb push_back
typedef long long llo;


vector<pair<llo,llo>> adj[300001];

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

ord xx[300001];
pair<llo,llo> fun[300001];
llo n,m;
llo cot=0;
llo dfs(llo no){

	vector<llo> cur;
	for(auto j:adj[no]){
		if(j.a>=n){
			fun[j.a]={-1,j.b};
			xx[j.a].insert({j.b,cot});
			cot++;
			xx[j.a].insert({j.b,cot});
			cot++;
			cur.pb(j.a);
		}
		else{
			llo x=dfs(j.a);
			cur.pb(x);
			llo la2=-1;
			while(xx[x].size()+fun[x].a>0){
				if(xx[x].size()+fun[x].a==1){
					la2=(*(xx[x].find_by_order(xx[x].size()-1))).a;
				}
				xx[x].erase(xx[x].find_by_order(xx[x].size()-1));
			}
			llo la=(*(xx[x].find_by_order(xx[x].size()-1))).a;
			if(la2==-1){
				la2=la;
			}
			fun[x].b+=j.b;
			if(xx[x].size()+fun[x].a==0){
				xx[x].erase(xx[x].find_by_order(xx[x].size()-1));
			}
			else{
				while(xx[x].size()+fun[x].a<0){
					xx[x].insert({la,cot});
					cot++;
				}
			}
			//sum is -1
			//xx[x].insert({la,cot});
			cot++;
			xx[x].insert({la+j.b,cot});
			cot++;
			xx[x].insert({la2+j.b,cot});
			cot++;
			/*if(no==1){
				cout<<fun[x].a<<":"<<fun[x].b<<endl;
				for(auto j:xx[x]){
					cout<<j.a<<",";
				}
				cout<<endl;
			}*/
			//fun[x].a+=-1;
			//fun[x].b+=j.b;
		}

	}
	pair<llo,llo> ma={-1,-1};
	for(auto j:cur){
		ma=max(ma,{(llo)xx[j].size(),j});
	}
	for(auto j:cur){
		if(j!=ma.b){
			for(auto jj:xx[j]){
				xx[ma.b].insert(jj);
			}
			fun[ma.b].a+=fun[j].a;
			fun[ma.b].b+=fun[j].b;
		}
	}
	/*cout<<no<<"::"<<ma.b<<endl;
	cout<<fun[ma.b].a<<";"<<fun[ma.b].b<<endl;
	for(auto j:xx[ma.b]){
		cout<<j.a<<",";
	}
	cout<<endl;*/
	return ma.b;




}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	
	cin>>n>>m;
	for(llo i=1;i<n+m;i++){
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		adj[aa].pb({i,bb});
	}


	llo ha=dfs(0);
	llo ans=fun[ha].a;
	vector<int> ne;
	for(auto j:xx[ha]){
		ne.pb(j.a);
	}
	llo val=fun[ha].b;
	llo pr=0;
	for(int i=0;i<ne.size();i++){
		if(fun[ha].a==0){
			break;
		}
		val+=fun[ha].a*(ne[i]-pr);
		pr=ne[i];
		fun[ha].a+=1;
	}
	cout<<val<<endl;
	/*cout<<fun[ha].a<<"::"<<fun[ha].b<<endl;
	for(auto j:xx[ha]){
		cout<<j.a<<",";
	}
	cout<<endl;


*/






	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:124:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i=0;i<ne.size();i++){
      |              ~^~~~~~~~~~
fireworks.cpp:117:6: warning: unused variable 'ans' [-Wunused-variable]
  117 |  llo ans=fun[ha].a;
      |      ^~~

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