Submission #26406

#	Time	Username	Problem	Language	Result	Execution time	Memory
26406		zscoder	Fireworks (APIO16_fireworks)	C++14	100 / 100	313 ms	61192 KiB

fireworks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

priority_queue<ll>* dp[300001];
vi adj[300001];
ll par[300001];
ll a[300001];
ll b[300001];

void dfs(int u)
{
	//cerr<<u<<' '<<par[u]<<'\n';
	if(adj[u].empty())
	{
		dp[u] = new priority_queue<ll>;
		dp[u]->push(par[u]);
		dp[u]->push(par[u]);
		a[u]=1;
		b[u]=-par[u];
		return ;
	}
	int lc = -1; int siz = 0;
	for(int i = 0; i < adj[u].size(); i++)
	{
		int v = adj[u][i];
		dfs(v);
		if(dp[v]->size()>siz)
		{
			siz=dp[v]->size();
			lc=v;
		}
	}
	dp[u]=dp[lc];
	a[u]=a[lc];
	b[u]=b[lc];
	for(int i=0;i<adj[u].size();i++)
	{
		int v = adj[u][i];
		if(v!=lc)
		{
			while(!dp[v]->empty())
			{
				dp[u]->push(dp[v]->top());
				dp[v]->pop();
			}
			a[u]+=a[v];
			b[u]+=b[v];
		}
	}
	while(a[u]>1)
	{
		ll x = dp[u]->top();
		a[u]--;
		b[u]+=x;
		dp[u]->pop();
	}
	if(u==0)
	{
		while(a[u]>0)
		{
			ll x = dp[u]->top();
			a[u]--;
			b[u]+=x;
			dp[u]->pop();
		}
		cout<<b[u]<<'\n';
		exit(0);
	}
	ll u1=dp[u]->top();
	dp[u]->pop();
	ll u2=dp[u]->top();
	dp[u]->pop();
	dp[u]->push(u2+par[u]);
	dp[u]->push(u1+par[u]);
	b[u]-=par[u];
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m; cin>>n>>m;
	par[0]=0;
	n+=m;
	for(int i=1;i<n;i++)
	{
		int u; cin>>u;
		u--;
		cin>>par[i];
		adj[u].pb(i);
	}
	dfs(0);
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++)
                   ^
fireworks.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(dp[v]->size()>siz)
                   ^
fireworks.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[u].size();i++)
               ^

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