oj.uz

Submission #605939

# Submission time Handle Problem Language Result Execution time Memory
605939 2022-07-26T04:28:43 Z GusterGoose27 Fireworks (APIO16_fireworks) C++11
26 / 100
 9 ms 7420 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

class hull {
public:
	ll init_val = 0;
	int init_slope = 0;
	multiset<ll> changes;
	hull() {}
	void prune(int length) {
		init_val += length;
		if (changes.empty()) {
			changes.insert(length);
			changes.insert(length);
			init_slope = -1;
			return;
		}
		while (changes.size() > -init_slope+1) changes.erase(changes.find(*changes.rbegin()));
		auto it = changes.rbegin();
		ll b2 = *it;
		changes.erase(changes.find(*it));
		it = changes.rbegin();
		ll b1 = *it;
		changes.erase(changes.find(*it));
		changes.insert(b1+length);
		changes.insert(b2+length);
	}
	void merge(hull *other) {
		init_val += other->init_val;
		init_slope += other->init_slope;
		for (ll v: other->changes) changes.insert(v);
		delete other;
	}
	int size() {
		return changes.size();
	}
};

const int MAXN = 3e5;
int n, m;
vector<pii> edges[MAXN];
hull *hulls[MAXN];

void dfs(int cur = 0) {
	hulls[cur] = new hull();
	for (pii e: edges[cur]) {
		int next = e.first;
		dfs(next);
		hulls[next]->prune(e.second);
		if (hulls[cur]->size() > hulls[next]->size()) hulls[cur]->merge(hulls[next]);
		else {
			hulls[next]->merge(hulls[cur]);
			hulls[cur] = hulls[next];
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i < n+m; i++) {
		int p, w;
		cin >> p >> w; p--;
		edges[p].push_back(pii(i, w));
	}
	dfs();
	hull *h = hulls[0];
	ll v = h->init_val;
	int slope = h->init_slope;
	ll prev = 0;
	for (int change: h->changes) {
		v += slope*(change-prev);
		slope++;
		if (slope == 0) break;
		prev = change;
	}
	cout << v << "\n";
}

Compilation message

fireworks.cpp: In member function 'void hull::prune(int)':
fireworks.cpp:22:25: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |   while (changes.size() > -init_slope+1) changes.erase(changes.find(*changes.rbegin()));
      |          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7368 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7272 KB Output is correct
5 Correct 5 ms 7368 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 4 ms 7368 KB Output is correct
10 Correct 5 ms 7368 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7252 KB Output is correct
2 Correct 4 ms 7420 KB Output is correct
3 Correct 5 ms 7400 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7340 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 5 ms 7380 KB Output is correct
12 Correct 6 ms 7380 KB Output is correct
13 Correct 9 ms 7348 KB Output is correct
14 Correct 6 ms 7380 KB Output is correct
15 Correct 5 ms 7372 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 5 ms 7380 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7376 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7368 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7272 KB Output is correct
5 Correct 5 ms 7368 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 4 ms 7368 KB Output is correct
10 Correct 5 ms 7368 KB Output is correct
11 Correct 6 ms 7252 KB Output is correct
12 Correct 4 ms 7420 KB Output is correct
13 Correct 5 ms 7400 KB Output is correct
14 Correct 5 ms 7372 KB Output is correct
15 Correct 5 ms 7380 KB Output is correct
16 Correct 5 ms 7340 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 4 ms 7252 KB Output is correct
19 Correct 4 ms 7252 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct
21 Correct 5 ms 7380 KB Output is correct
22 Correct 6 ms 7380 KB Output is correct
23 Correct 9 ms 7348 KB Output is correct
24 Correct 6 ms 7380 KB Output is correct
25 Correct 5 ms 7372 KB Output is correct
26 Correct 4 ms 7380 KB Output is correct
27 Correct 5 ms 7380 KB Output is correct
28 Correct 4 ms 7380 KB Output is correct
29 Correct 4 ms 7376 KB Output is correct
30 Incorrect 8 ms 7368 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7368 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7272 KB Output is correct
5 Correct 5 ms 7368 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 4 ms 7368 KB Output is correct
10 Correct 5 ms 7368 KB Output is correct
11 Correct 6 ms 7252 KB Output is correct
12 Correct 4 ms 7420 KB Output is correct
13 Correct 5 ms 7400 KB Output is correct
14 Correct 5 ms 7372 KB Output is correct
15 Correct 5 ms 7380 KB Output is correct
16 Correct 5 ms 7340 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 4 ms 7252 KB Output is correct
19 Correct 4 ms 7252 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct
21 Correct 5 ms 7380 KB Output is correct
22 Correct 6 ms 7380 KB Output is correct
23 Correct 9 ms 7348 KB Output is correct
24 Correct 6 ms 7380 KB Output is correct
25 Correct 5 ms 7372 KB Output is correct
26 Correct 4 ms 7380 KB Output is correct
27 Correct 5 ms 7380 KB Output is correct
28 Correct 4 ms 7380 KB Output is correct
29 Correct 4 ms 7376 KB Output is correct
30 Incorrect 8 ms 7368 KB Output isn't correct
31 Halted 0 ms 0 KB -