Submission #485766

#	Time	Username	Problem	Language	Result	Execution time	Memory
485766		milisav	Fireworks (APIO16_fireworks)	C++14	7 / 100	14 ms	23772 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 x[maxn][2];
long long t[maxn];
vector<long long> cur;
void dfs(int u) {
	if(a[u].size()==0) {
		x[u][0]=c[u];
		x[u][1]=c[u];
		return;
	}
	for(auto v:a[u]) {
		dfs(v);
	}
	cur.clear();
	for(auto v:a[u]) {
		cur.push_back(x[v][0]);
		cur.push_back(x[v][1]);
	}
	sort(cur.begin(),cur.end());
	int pos=cur.size()/2-1;
	x[u][0]=cur[pos]+c[u];
	x[u][1]=cur[pos+1]+c[u];
	long long p=cur[pos];
	for(auto v:a[u]) {
		t[u]+=t[v];
		if(p<x[v][0]) t[u]+=(x[v][0]-p);
		if(p>x[v][1]) t[u]+=(p-x[v][1]);
	}
}
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",t[1]);
	return 0;
}

Compilation message (stderr)

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

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