Submission #47680

#	Time	Username	Problem	Language	Result	Execution time	Memory
47680		E869120	Fireworks (APIO16_fireworks)	C++14	7 / 100	9 ms	7936 KiB

fireworks

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

long long N, M, A[300009], B[300009], dist[300009]; vector<pair<long long, long long>>x[300009];
long long L[300009], R[300009], cost[300009];

void dfs(int pos, long long depth) {
	dist[pos] = depth;
	for (int i = 0; i < x[pos].size(); i++) dfs(x[pos][i].first, depth + x[pos][i].second);
}
void solve(int pos) {
	if (x[pos].size() == 0) { L[pos] = dist[pos]; R[pos] = dist[pos]; cost[pos] = 0; return; }
	
	for (int i = 0; i < x[pos].size(); i++) solve(x[pos][i].first);

	vector<long long>D;
	for (int i = 0; i < x[pos].size(); i++) {
		D.push_back(L[x[pos][i].first]);
		D.push_back(R[x[pos][i].first]);
	}
	sort(D.begin(), D.end());
	L[pos] = D[D.size() / 2 - 1]; R[pos] = D[D.size() / 2];

	for (int i = 0; i < x[pos].size(); i++) {
		int to = x[pos][i].first; cost[pos] += cost[to];
		if (L[to] <= L[pos] && L[pos] <= R[to]) continue;
		cost[pos] += min(abs(L[to] - L[pos]), abs(R[to] - L[pos]));
	}
}

int main() {
	cin >> N >> M;
	for (int i = 2; i <= N + M; i++) {
		scanf("%lld%lld", &A[i], &B[i]);
		x[A[i]].push_back(make_pair(i, B[i]));
	}
	dfs(1, 0);
	solve(1);
	cout << cost[1] << endl;
	return 0;
}

Compilation message (stderr)

fireworks.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
fireworks.cpp: In function 'void dfs(int, long long int)':
fireworks.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x[pos].size(); i++) dfs(x[pos][i].first, depth + x[pos][i].second);
                  ~~^~~~~~~~~~~~~~~
fireworks.cpp: In function 'void solve(int)':
fireworks.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x[pos].size(); i++) solve(x[pos][i].first);
                  ~~^~~~~~~~~~~~~~~
fireworks.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
fireworks.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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