Submission #485767

#	Time	Username	Problem	Language	Result	Execution time	Memory
485767		milisav	Fireworks (APIO16_fireworks)	C++14	7 / 100	13 ms	23816 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;
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 t1=cur[pos];
	long long t2=cur[pos+1];
	long long v1=0,v2=0;
	for(auto v:a[u]) {
		if(t1<x[v][0]) v1+=(x[v][0]-t1);
		if(t1>x[v][1]) v1+=(t1-x[v][1]);
		if(t2<x[v][0]) v2+=(x[v][0]-t2);
		if(t2>x[v][1]) v2+=(t2-x[v][1]);
	}
	assert(v1==v2);
	ans+=v1;
}
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:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
fireworks.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d %d",&p[i],&c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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