Submission #154114

#	Time	Username	Problem	Language	Result	Execution time	Memory
154114		junhopark	Fireworks (APIO16_fireworks)	C++14	100 / 100	403 ms	66044 KiB

fireworks

#include <bits/stdc++.h>
#define eb emplace_back
#define all(V) (V).begin(),(V).end()
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 3e5+5;
int n, m, piv, ch[SZ], si[SZ];
int pl[SZ], l[SZ], sub[SZ];
LL dep[SZ], sum;
priority_queue<LL> pq[SZ];
vector<pii> v[SZ];
vector<LL> res, test;
void get_dep(int now)
{
	ch[now]=sub[now]=1;
	for (pii c:v[now]) {
		dep[c.fi]=dep[now]+1;
		get_dep(c.fi);
		sub[now]+=sub[c.fi];
	}
}
void solve(int now)
{
	if (now>n) {
		pl[now]=++piv;
		pq[piv].emplace(l[now]);
		pq[piv].emplace(l[now]);
		si[piv]=-1;
		return;
	}
	LL len;
	int p, maxi=-1;
	for (pii c:v[now]) {
		solve(c.fi);
		if (maxi<(int)pq[pl[c.fi]].size()) {
			maxi=(int)pq[pl[c.fi]].size();
			p=c.fi;
			len=l[c.fi];
		}
	}
	pl[now]=pl[p];
	for (pii c:v[now]) {
		if (c.fi==p) continue;
		si[pl[now]]+=si[pl[c.fi]];
		while (pq[pl[c.fi]].size()) {
			pq[pl[now]].emplace(pq[pl[c.fi]].top());
			pq[pl[c.fi]].pop();
		}
	}
	if (now>1) {
		LL cnt=si[pl[now]]+(int)pq[pl[now]].size()-1;
		while (cnt--) pq[pl[now]].pop();
		LL a, b, c;
		a=pq[pl[now]].top();
		pq[pl[now]].pop();
		b=pq[pl[now]].top();
		pq[pl[now]].pop();
		c=pq[pl[now]].top();
		a+=l[now],b+=l[now];
		pq[pl[now]].emplace(a);
		pq[pl[now]].emplace(b);
	}
}
int main()
{
	int i, a, b;
	scanf("%d %d", &n, &m);
	for (i=2; i<=n+m; i++) {
		scanf("%d %d", &a, &b);
		v[a].eb(i,b);
		l[i]=b;
		sum+=b;
	}
	get_dep(1);
	solve(1);
	while (pq[pl[1]].size()) {
		res.eb(pq[pl[1]].top());
		pq[pl[1]].pop();
	}
	LL prev=0, pp=res.size()-1;
	while (si[pl[1]]<0) {
		sum+=(res[pp]-prev)*si[pl[1]];
		si[pl[1]]++;
		prev=res[pp--];
	}
	printf("%lld\n", sum);
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void solve(int)':
fireworks.cpp:56:12: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   LL a, b, c;
            ^
fireworks.cpp:34:5: warning: variable 'len' set but not used [-Wunused-but-set-variable]
  LL len;
     ^~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:70: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:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'void solve(int)':
fireworks.cpp:44:14: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  pl[now]=pl[p];
          ~~~~^

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