Submission #47692

#	Time	Username	Problem	Language	Result	Execution time	Memory
47692		E869120	Fireworks (APIO16_fireworks)	C++14	55 / 100	2094 ms	360868 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], sum; vector<pair<long long, long long>>x[300009];
vector<long long>G[300009];

void dfs1(int pos, long long depth) {
	dist[pos] = depth;
	for (int i = 0; i < x[pos].size(); i++) dfs1(x[pos][i].first, depth + x[pos][i].second);
}
void dfs2(int pos) {
	if (x[pos].size() == 0) { G[pos].push_back(dist[pos]); G[pos].push_back(dist[pos]); return; }

	for (int i = 0; i < x[pos].size(); i++) dfs2(x[pos][i].first);

	for (int i = 0; i < x[pos].size(); i++) {
		for (int j = 0; j < G[x[pos][i].first].size(); j++) G[pos].emplace_back(G[x[pos][i].first][j]);
	}
	sort(G[pos].begin(), G[pos].end());
	vector<long long>H;
	for (int i = 0; i < (int)G[pos].size() - (int)x[pos].size() + 1; i++) H.emplace_back(G[pos][i]);
	G[pos] = H;
	for (int i = 0; i < (int)G[pos].size() - 2; i++) G[pos][i] -= B[pos];
}

int main() {
	cin >> N >> M;
	for (int i = 2; i <= N + M; i++) {
		scanf("%lld%lld", &A[i], &B[i]); sum += B[i];
		x[A[i]].push_back(make_pair(i, B[i]));
	}
	dfs1(1, 0);
	dfs2(1);
	long long ret = sum, cx = 0, D = G[1].size() - 1;
	for (int i = 0; i < G[1].size() - 1; i++) { ret -= (G[1][i] - cx)*D; cx = G[1][i]; D--; }
	cout << ret << 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 dfs1(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++) dfs1(x[pos][i].first, depth + x[pos][i].second);
                  ~~^~~~~~~~~~~~~~~
fireworks.cpp: In function 'void dfs2(int)':
fireworks.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x[pos].size(); i++) dfs2(x[pos][i].first);
                  ~~^~~~~~~~~~~~~~~
fireworks.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
fireworks.cpp:20:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < G[x[pos][i].first].size(); j++) G[pos].emplace_back(G[x[pos][i].first][j]);
                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[1].size() - 1; i++) { ret -= (G[1][i] - cx)*D; cx = G[1][i]; D--; }
                  ~~^~~~~~~~~~~~~~~~~
fireworks.cpp:32: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]); sum += B[i];
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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