oj.uz

Submission #551162

# Submission time Handle Problem Language Result Execution time Memory
551162 2022-04-20T00:40:43 Z pavement Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 2000 ms 122744 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, idx, totC, totR, A[200005], H[200005], C[200005];
vector<int> adj[200005];
ordered_set<iii> S[200005];

void dp(int n, int e = -1) {
	for (auto u : adj[n]) if (u != e) {
		dp(u, n);
		if (S[u].size() > S[n].size()) swap(S[n], S[u]);
		for (auto i : S[u]) S[n].insert(i);
	}
	vector<ordered_set<iii>::iterator> to_del;
	auto it = S[n].upper_bound(mt(H[n], LLONG_MAX, LLONG_MAX));
	for (int bal = C[n]; bal > 0 && it != S[n].end(); it++) {
		auto [h, c, tmp] = *it;
		if (bal > c) {
			to_del.pb(it);
			bal -= c;
		} else if (bal == c) {
			to_del.pb(it);
			bal = 0;
		} else {
			to_del.pb(it);
			S[n].insert(mt(h, c - bal, ++idx));
			bal = 0;
		}
	}
	S[n].insert(mt(H[n], C[n], ++idx));
	for (auto i : to_del) S[n].erase(i);
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> H[i] >> C[i];
		H[i] = -H[i];
		if (i > 1) adj[A[i]].pb(i);
		totC += C[i];
	}
	// solving tree case
	dp(1);
	for (auto [a, b, c] : S[1]) totR += b;
	cout << totC - totR << '\n';
}

Compilation message

worst_reporter2.cpp:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main() {
      | ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26956 KB Output is correct
2 Correct 19 ms 26956 KB Output is correct
3 Correct 18 ms 26952 KB Output is correct
4 Correct 19 ms 26872 KB Output is correct
5 Correct 27 ms 28664 KB Output is correct
6 Correct 28 ms 28788 KB Output is correct
7 Correct 33 ms 28276 KB Output is correct
8 Correct 33 ms 28568 KB Output is correct
9 Correct 31 ms 28544 KB Output is correct
10 Correct 28 ms 28448 KB Output is correct
11 Correct 27 ms 28768 KB Output is correct
12 Correct 51 ms 28380 KB Output is correct
13 Correct 83 ms 28616 KB Output is correct
14 Correct 40 ms 27928 KB Output is correct
15 Correct 40 ms 27844 KB Output is correct
16 Correct 30 ms 28928 KB Output is correct
17 Correct 28 ms 28944 KB Output is correct
18 Correct 29 ms 29464 KB Output is correct
19 Correct 195 ms 28392 KB Output is correct
20 Correct 135 ms 28260 KB Output is correct
21 Correct 158 ms 28320 KB Output is correct
22 Correct 24 ms 28000 KB Output is correct
23 Correct 24 ms 27988 KB Output is correct
24 Correct 392 ms 28456 KB Output is correct
25 Correct 250 ms 28420 KB Output is correct
26 Correct 21 ms 28372 KB Output is correct
27 Correct 109 ms 28420 KB Output is correct
28 Correct 208 ms 28556 KB Output is correct
29 Correct 369 ms 28836 KB Output is correct
30 Correct 273 ms 28520 KB Output is correct
31 Correct 300 ms 28464 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26956 KB Output is correct
2 Correct 19 ms 26956 KB Output is correct
3 Correct 18 ms 26952 KB Output is correct
4 Correct 19 ms 26872 KB Output is correct
5 Correct 27 ms 28664 KB Output is correct
6 Correct 28 ms 28788 KB Output is correct
7 Correct 33 ms 28276 KB Output is correct
8 Correct 33 ms 28568 KB Output is correct
9 Correct 31 ms 28544 KB Output is correct
10 Correct 28 ms 28448 KB Output is correct
11 Correct 27 ms 28768 KB Output is correct
12 Correct 51 ms 28380 KB Output is correct
13 Correct 83 ms 28616 KB Output is correct
14 Correct 40 ms 27928 KB Output is correct
15 Correct 40 ms 27844 KB Output is correct
16 Correct 30 ms 28928 KB Output is correct
17 Correct 28 ms 28944 KB Output is correct
18 Correct 29 ms 29464 KB Output is correct
19 Correct 195 ms 28392 KB Output is correct
20 Correct 135 ms 28260 KB Output is correct
21 Correct 158 ms 28320 KB Output is correct
22 Correct 24 ms 28000 KB Output is correct
23 Correct 24 ms 27988 KB Output is correct
24 Correct 392 ms 28456 KB Output is correct
25 Correct 250 ms 28420 KB Output is correct
26 Correct 21 ms 28372 KB Output is correct
27 Correct 109 ms 28420 KB Output is correct
28 Correct 208 ms 28556 KB Output is correct
29 Correct 369 ms 28836 KB Output is correct
30 Correct 273 ms 28520 KB Output is correct
31 Correct 300 ms 28464 KB Output is correct
32 Correct 29 ms 28620 KB Output is correct
33 Correct 516 ms 108476 KB Output is correct
34 Correct 586 ms 107956 KB Output is correct
35 Correct 574 ms 104588 KB Output is correct
36 Correct 524 ms 108252 KB Output is correct
37 Correct 535 ms 104884 KB Output is correct
38 Correct 600 ms 122744 KB Output is correct
39 Execution timed out 2073 ms 87292 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26956 KB Output is correct
2 Correct 19 ms 26956 KB Output is correct
3 Correct 18 ms 26952 KB Output is correct
4 Correct 19 ms 26872 KB Output is correct
5 Correct 27 ms 28664 KB Output is correct
6 Correct 28 ms 28788 KB Output is correct
7 Correct 33 ms 28276 KB Output is correct
8 Correct 33 ms 28568 KB Output is correct
9 Correct 31 ms 28544 KB Output is correct
10 Correct 28 ms 28448 KB Output is correct
11 Correct 27 ms 28768 KB Output is correct
12 Correct 51 ms 28380 KB Output is correct
13 Correct 83 ms 28616 KB Output is correct
14 Correct 40 ms 27928 KB Output is correct
15 Correct 40 ms 27844 KB Output is correct
16 Correct 30 ms 28928 KB Output is correct
17 Correct 28 ms 28944 KB Output is correct
18 Correct 29 ms 29464 KB Output is correct
19 Correct 195 ms 28392 KB Output is correct
20 Correct 135 ms 28260 KB Output is correct
21 Correct 158 ms 28320 KB Output is correct
22 Correct 24 ms 28000 KB Output is correct
23 Correct 24 ms 27988 KB Output is correct
24 Correct 392 ms 28456 KB Output is correct
25 Correct 250 ms 28420 KB Output is correct
26 Correct 21 ms 28372 KB Output is correct
27 Correct 109 ms 28420 KB Output is correct
28 Correct 208 ms 28556 KB Output is correct
29 Correct 369 ms 28836 KB Output is correct
30 Correct 273 ms 28520 KB Output is correct
31 Correct 300 ms 28464 KB Output is correct
32 Correct 29 ms 28620 KB Output is correct
33 Correct 516 ms 108476 KB Output is correct
34 Correct 586 ms 107956 KB Output is correct
35 Correct 574 ms 104588 KB Output is correct
36 Correct 524 ms 108252 KB Output is correct
37 Correct 535 ms 104884 KB Output is correct
38 Correct 600 ms 122744 KB Output is correct
39 Execution timed out 2073 ms 87292 KB Time limit exceeded
40 Halted 0 ms 0 KB -