oj.uz

Submission #935027

# Submission time Handle Problem Language Result Execution time Memory
935027 2024-02-28T12:08:44 Z vjudge1 Fireworks (APIO16_fireworks) C++17
7 / 100
 3 ms 7516 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int N = 300005;
vector <pair<int,int> > adj[N];

array<int,3> dfs(int node) {
	int ans = 0, l=0, r=0;
	vector <pair<int, bool> > p;
	for(auto &[to, w] : adj[node]) {
		auto res = dfs(to);
		ans += res[0];
		p.push_back({res[1] + w, 0});
		p.push_back({res[2] + w, 1});
	}
	sort(p.begin(), p.end());
	int b = 0, a = adj[node].size();
	for(int i = 0; i < p.size(); i++) {
		if(p[i].second) {
			b++;
		}
		else {
			a--;
		}
		if(a == b) {
			l = p[i].first;
			r = p[i+1].first;
			if(i + 1 == p.size()) {
				cout << "WHAT?\n";
				exit(23);
			}
			break;
		}
	}
	for(int i = 0; i < p.size(); i++) {
		if(p[i].second) {
			ans += max(0ll, l - p[i].first);
		}
		else {
			ans += max(0ll, p[i].first - l);
		}
	}
	return {ans, l, r};
}

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	for(int i = 2; i <= n + m; i++) {
		int a, w;
		cin >> a >> w;
		adj[a].push_back({i, w});
	}
	cout << dfs(1)[0];
}

Compilation message

fireworks.cpp: In function 'std::array<long long int, 3> dfs(long long int)':
fireworks.cpp:20:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < p.size(); i++) {
      |                 ~~^~~~~~~~~~
fireworks.cpp:30:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    if(i + 1 == p.size()) {
      |       ~~~~~~^~~~~~~~~~~
fireworks.cpp:37:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = 0; i < p.size(); i++) {
      |                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7264 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7504 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7264 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7504 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Incorrect 3 ms 7256 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7264 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7504 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Incorrect 3 ms 7256 KB Output isn't correct
14 Halted 0 ms 0 KB -