제출 #98185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98185		fefe	Fireworks (APIO16_fireworks)	C++17	7 / 100	21 ms	16896 KiB

fireworks

#include<bits/stdc++.h>
#define MAX_N 300005
#define MAX_M 100005
#define pb push_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))
#define fi first
#define se second
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 0x3fffffff
#define MOD 1000000007LL
#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;
LL n,m,ln;
LL loc[MAX_N],base[MAX_N];
priority_queue<pil> pq[MAX_N];
vector<pil> adj[MAX_N],lst;
void merge(LL x,LL y){
	LL p=loc[x],q=loc[y];
	if(pq[q].size()>pq[p].size())	swap(p,q);
	loc[x]=p;base[p]+=base[q];
	while(pq[q].size()){
		pq[p].push(pq[q].top());
		pq[q].pop();
	}
}
void dfs(LL x,LL v){
	loc[x]=ln++;
	for(pil p:adj[x]){
		if(!adj[p.fi].size()){pq[loc[x]].push({p.se,1});pq[loc[x]].push({p.se,-1});}
		else{
			dfs(p.fi,p.se);
			merge(x,p.fi);
		}
	}
	//line-up
	//base[x]+=v;
	reset(lst);
	pil p;
	while(pq[loc[x]].size()){
		p=pq[loc[x]].top();
		lst.pb({p.fi,p.se});
		pq[loc[x]].pop();
	}
	LL sz=lst.size();
	pq[loc[x]].push({lst[sz/2].fi+v,-1});
	pq[loc[x]].push({lst[sz/2-1].fi+v,1});
	for(int i=0;i<sz;i++){
		base[loc[x]]+=max((lst[sz/2].fi-lst[i].fi)*lst[i].se,0LL);
	}
}
int main(){
	LL i,x,v;
	scanf("%lld %lld",&n,&m);n+=m;
	for(i=2;i<=n;i++){
		scanf("%lld %lld",&x,&v);
		adj[x].pb({i,v});
	}
	dfs(1,0);
	printf("%lld\n",base[loc[1]]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fireworks.cpp: In function 'int main()':
fireworks.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&m);n+=m;
  ~~~~~^~~~~~~~~~~~~~~~~~~
fireworks.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&x,&v);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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