Submission #485769

#	Time	Username	Problem	Language	Result	Execution time	Memory
485769		milisav	Fireworks (APIO16_fireworks)	C++14	100 / 100	420 ms	151032 KiB

fireworks

#include<bits/stdc++.h>
#define maxn 1000000
using namespace std;
int n,m;
vector<int> a[maxn];
int p[maxn];
int c[maxn];
long long ans;
multiset<long long> x[maxn];
long long t[maxn];
int pt[maxn];
vector<long long> cur;
void dfs(int u) {
	if(a[u].size()==0) {
		x[u].insert(c[u]);
		x[u].insert(c[u]);
		pt[u]=u;
		t[u]=c[u];
		return;
	}
	for(auto v:a[u]) {
		dfs(v);
	}
	pt[u]=0;
	for(auto v:a[u]) {
		if(x[pt[v]].size()>x[pt[u]].size()) {
			pt[u]=pt[v];
		}
	}
	for(auto v:a[u]) {
		if(pt[u]!=pt[v]) {
			for(auto c:x[pt[v]]) {
				x[pt[u]].insert(c);
			}
		}
	}
	int sz=a[u].size();
	long long sum=0;
	for(int i=0;i<sz-1;i++) {
		sum+=(*x[pt[u]].rbegin());
		x[pt[u]].erase(--x[pt[u]].end());
	}
	long long p1=(*x[pt[u]].rbegin());
	x[pt[u]].erase(--x[pt[u]].end());
	long long p2=(*x[pt[u]].rbegin());
	x[pt[u]].erase(--x[pt[u]].end());
	x[pt[u]].insert(p1+c[u]);
	x[pt[u]].insert(p2+c[u]);
	t[u]=p1+c[u];
	ans+=(sum-(sz-1)*p1);
	for(auto v:a[u]) {
		ans+=(p1-t[v]);
	}
}
int main() {
	scanf("%d %d",&n,&m);
	for(int i=2;i<=n+m;i++) {
		scanf("%d %d",&p[i],&c[i]);
		a[p[i]].push_back(i);
	}
	dfs(1);
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

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

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