Submission #1081849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081849		vjudge1	Fireworks (APIO16_fireworks)	C++17	100 / 100	268 ms	23904 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
int n, m;
int pr[300005], cnt[300005], c[300005];//父亲，儿子数量，边权
int cur, rt[300005];//可并堆节点数，可并堆中以原树每个点为根的堆的根
long long ans;
//左偏树(维护大根堆) 部分 
//注意，拐点之间k差为1(允许有重的拐点) 
struct LeftistHeap{
	int l, r, d; 
	long long val;//val在实际存储中表示拐点的横坐标 
} p[600005]; 
#define ls p[k1].l
#define rs p[k1].r
int Mrg(int k1, int k2){
	if(!k1 || !k2) return (k1 + k2);
	if(p[k1].val < p[k2].val) swap(k1, k2);
	rs = Mrg(rs, k2);
	if(p[ls].d < p[rs].d) swap(ls, rs);
	if(!rs)	p[k1].d = 0;
	else	p[k1].d = p[rs].d + 1;
	return k1;
}
void pop(int k){ int k1 = rt[k]; rt[k] = Mrg(ls, rs);}
void push(int k1, int a){rt[k1] = Mrg(rt[k1], a);}
#undef ls
#undef rs
int main(){
	scanf("%d %d", &n, &m);
	//ans先设定为f(0)再逐步向右推出答案 
	for(int i = 2; i <= n + m; i++){
		scanf("%d %d", &pr[i], &c[i]);
		cnt[pr[i]]++, ans += c[i];
	}
	for(int i = n + m; i >= 2; i--){//根据p[i] < i的性质可以直接这样从下到上遍历树 
		//提取出斜率为零的那一段
		//printf("%d\n", i);
		long long l, r;
		l = r = 0;
		if(i <= n){//非叶节点 
			//弹出后面点, 同时完成将后面斜率修成1
			while(cnt[i] >= 2) pop(i), cnt[i]--;
			r = p[rt[i]].val; pop(i);
			l = p[rt[i]].val; pop(i);
		}
		//右移斜率为零的那一段
		p[++cur].val = l + c[i], push(i, cur);
		p[++cur].val = r + c[i], push(i, cur);
		//合并儿子 
		push(pr[i], rt[i]);
	}
	while(cnt[1] >= 1) pop(1), cnt[1]--;
	//从左向右减推出答案
	while(rt[1]) ans -= p[rt[1]].val, pop(1);//每一次的点在它后面还会再减，从而满足斜率	
	printf("%lld\n", ans); 
	return 0;
}

Compilation message (stderr)

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

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