Submission #1068929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068929		vjudge1	Fireworks (APIO16_fireworks)	C++14	100 / 100	194 ms	23984 KiB

fireworks

//writer:Oier_szc

#include <bits/stdc++.h>
#define ED cerr<<endl;
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define cr4(x,y,z,w) cerr<<x<<" "<<y<<" "<<z<<" "<<w<<endl;
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=3e5+5,INF=2e9,mod=1e9+7;
int n,m;
int fa[N],c[N],deg[N];
int rt[N],idx=0;
ll ans=0;

struct tree {
	int l,r,dis;
	ll v;
}tr[N<<1];

int merge(int x,int y) {
	if(!x||!y) return x|y;
	if(tr[x].v<tr[y].v) swap(x,y);
	tr[x].r=merge(tr[x].r,y);
	if(tr[tr[x].l].dis<tr[tr[x].r].dis) {
		swap(tr[x].l,tr[x].r);
	}
	tr[x].dis=tr[tr[x].r].dis+1;
	return x;
}

inline int pop(int x) {
	return merge(tr[x].l,tr[x].r);
}

int main()
{
	tr[0].dis=-1;
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n+m;++i) {
		scanf("%d%d",&fa[i],&c[i]);
		++deg[fa[i]],ans+=c[i];
	}
	for(int i=n+m;i>1;--i) {
		ll l=0,r=0;
		if(i<=n) {
			while(--deg[i]) rt[i]=pop(rt[i]);
			r=tr[rt[i]].v,rt[i]=pop(rt[i]);
			l=tr[rt[i]].v,rt[i]=pop(rt[i]);
		}
		tr[++idx].v=l+c[i],tr[++idx].v=r+c[i];
		rt[i]=merge(rt[i],merge(idx-1,idx));
		rt[fa[i]]=merge(rt[fa[i]],rt[i]);
	}
	while(deg[1]--) rt[1]=pop(rt[1]);
	while(rt[1]) ans-=tr[rt[1]].v,rt[1]=pop(rt[1]);
	printf("%lld",ans);
	return 0;
}
/*
人类智慧。
首先套路的DP是设dp[i][j]表示子树i然后距离为j。
可以发现转移是和一个绝对函数做加法卷积然后再把
所有的儿子合并起来。
其中加法卷积这一操作又可以分解成整体上移，整体右移，
添加斜率为-1的直线，将右边斜率整体推平为-1四个操作。
考虑用slope trick进行操作。 
由于j这一维规模极大所以考虑二次差分记录转折点。 
这样问题就变成了堆的插入，删除，合并。上左偏树即可。
最后统计答案，显然f(0)等于边权之和，然后容易借转折点
推出函数值。 
*/

Compilation message (stderr)

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

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