Submission #1022832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022832		vjudge1	Fireworks (APIO16_fireworks)	C++11	100 / 100	277 ms	35412 KiB

fireworks

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,fa[600005],w[600005],rd[600005];
int rt[600005],lc[600005],rc[600005],v[600005],dis[600005],tot,ans;
int getnew(int x){
	v[++tot]=x;return tot;
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(v[y]>v[x])swap(x,y);
	rc[x]=merge(rc[x],y);
	if(dis[lc[x]]<dis[rc[x]])swap(lc[x],rc[x]);
	dis[x]=dis[rc[x]]+1;
	return x;
}
signed main(){
	scanf("%lld%lld",&n,&m);dis[0]=-1;
	for(int i=2;i<=n+m;i++){
		scanf("%lld%lld",&fa[i],&w[i]);rd[fa[i]]++;
		ans+=w[i];
	}
	for(int i=n+m;i>=2;i--){
		int l=0,r=0;
		if(i<=n)while(rd[i]-->1)rt[i]=merge(lc[rt[i]],rc[rt[i]]);
		r=v[rt[i]],rt[i]=merge(lc[rt[i]],rc[rt[i]]);
		l=v[rt[i]],rt[i]=merge(lc[rt[i]],rc[rt[i]]);
		rt[i]=merge(rt[i],merge(getnew(l+w[i]),getnew(r+w[i])));
		rt[fa[i]]=merge(rt[fa[i]],rt[i]);
	}
	while(rd[1]--)rt[1]=merge(lc[rt[1]],rc[rt[1]]);
	while(rt[1])ans=ans-v[rt[1]],rt[1]=merge(lc[rt[1]],rc[rt[1]]);
	printf("%lld",ans);
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%lld%lld",&n,&m);dis[0]=-1;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
fireworks.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%lld%lld",&fa[i],&w[i]);rd[fa[i]]++;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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