oj.uz

Submission #47680

# Submission time Handle Problem Language Result Execution time Memory
47680 2018-05-06T08:44:02 Z E869120 Fireworks (APIO16_fireworks) C++14
7 / 100
 9 ms 7936 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7548 KB Output is correct
2 Correct 8 ms 7668 KB Output is correct
3 Correct 9 ms 7724 KB Output is correct
4 Correct 9 ms 7840 KB Output is correct
5 Correct 7 ms 7840 KB Output is correct
6 Correct 7 ms 7840 KB Output is correct
7 Correct 7 ms 7840 KB Output is correct
8 Correct 9 ms 7900 KB Output is correct
9 Correct 7 ms 7900 KB Output is correct
10 Correct 7 ms 7900 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7900 KB Output is correct
2 Correct 7 ms 7900 KB Output is correct
3 Incorrect 7 ms 7936 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7548 KB Output is correct
2 Correct 8 ms 7668 KB Output is correct
3 Correct 9 ms 7724 KB Output is correct
4 Correct 9 ms 7840 KB Output is correct
5 Correct 7 ms 7840 KB Output is correct
6 Correct 7 ms 7840 KB Output is correct
7 Correct 7 ms 7840 KB Output is correct
8 Correct 9 ms 7900 KB Output is correct
9 Correct 7 ms 7900 KB Output is correct
10 Correct 7 ms 7900 KB Output is correct
11 Correct 7 ms 7900 KB Output is correct
12 Correct 7 ms 7900 KB Output is correct
13 Incorrect 7 ms 7936 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7548 KB Output is correct
2 Correct 8 ms 7668 KB Output is correct
3 Correct 9 ms 7724 KB Output is correct
4 Correct 9 ms 7840 KB Output is correct
5 Correct 7 ms 7840 KB Output is correct
6 Correct 7 ms 7840 KB Output is correct
7 Correct 7 ms 7840 KB Output is correct
8 Correct 9 ms 7900 KB Output is correct
9 Correct 7 ms 7900 KB Output is correct
10 Correct 7 ms 7900 KB Output is correct
11 Correct 7 ms 7900 KB Output is correct
12 Correct 7 ms 7900 KB Output is correct
13 Incorrect 7 ms 7936 KB Output isn't correct
14 Halted 0 ms 0 KB -