Submission #113718

#	Time	Username	Problem	Language	Result	Execution time	Memory
113718		imyujin	Fireworks (APIO16_fireworks)	C++14	100 / 100	364 ms	82808 KiB

fireworks

#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

#define MAXN 300005

int n, m;
int p[MAXN];
long long c[MAXN];
int sz[MAXN];
vector<int> gph[MAXN];

struct func{
	priority_queue<long long> pq;
	long long cost;
	int slope;

	void init(){
		cost=0;
		slope=-1;
		pq.push(0);
		pq.push(0);
	}

	void upperize(int x){
		vector<long long> v;
		cost+=c[x];
		while(!pq.empty()&&slope+(int)pq.size()>1) pq.pop();
		while(!pq.empty()&&slope+(int)pq.size()>=0){
			v.push_back(pq.top());
			pq.pop();
		}
		while(!v.empty()){
			pq.push(v.back()+c[x]);
			v.pop_back();
		}
	}
}dp[MAXN];

bool cmp(int a, int b){
	return sz[a]>sz[b];
}

void dfs(int x){
	if(x>n){
		sz[x]=1;
		return;
	}
	for(int i=0; i<gph[x].size(); i++){
		dfs(gph[x][i]);
		sz[x]+=sz[gph[x][i]];
	}
	sort(gph[x].begin(), gph[x].end(), cmp);
}

int solve(int x){
	if(x>n){
		dp[x].init();
		return x;
	}

	int ret=solve(gph[x][0]);
	dp[ret].upperize(gph[x][0]);
	for(int i=1; i<gph[x].size(); i++){
		int t=solve(gph[x][i]);
		dp[t].upperize(gph[x][i]);
		dp[ret].cost+=dp[t].cost;
		dp[ret].slope+=dp[t].slope;
		while(!dp[t].pq.empty()){
			dp[ret].pq.push(dp[t].pq.top());
			dp[t].pq.pop();
		}
	}
	return ret;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i=2; i<=n+m; i++) scanf("%d%lld", p+i, c+i);
	
	for(int i=2; i<=n+m; i++) gph[p[i]].push_back(i);
	dfs(1);
	func ret=dp[solve(1)];
	ret.upperize(0);
	long long ansp=ret.pq.top();
	long long ans=ret.cost+ansp*ret.slope;
	while(!ret.pq.empty()){
		ans+=ansp-ret.pq.top();
		ret.pq.pop();
	}

	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gph[x].size(); i++){
               ~^~~~~~~~~~~~~~
fireworks.cpp: In function 'int solve(int)':
fireworks.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<gph[x].size(); i++){
               ~^~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:82:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=2; i<=n+m; i++) scanf("%d%lld", p+i, c+i);
                            ~~~~~^~~~~~~~~~~~~~~~~~~~

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