oj.uz

Submission #725221

# Submission time Handle Problem Language Result Execution time Memory
725221 2023-04-17T03:55:03 Z pavement Magic Tree (CEOI19_magictree) C++17
50 / 100
 2000 ms 51576 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;
#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)
#define g4(a) get<4>(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>;
using iiiii = tuple<int, 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, m, k, ans;
vector<int> adj[100005];
vector<ii> vec[100005];
map<int, int> M[100005], mpp[100005];

void dp(int u) {
	for (auto v : adj[u]) {
		dp(v);
		if (M[u].size() < M[v].size()) swap(M[u], M[v]);
		for (auto i : M[v]) M[u][i.first] += i.second;
	}
	int cur = 0;
	vector<int> eval;
	auto it = M[u].begin();
	for (auto [t, val] : vec[u]) {
		while (it != M[u].end() && it->first <= t) {
			cur += it->second;
			++it;
		}
		eval.pb(cur);
	}
	reverse(eval.begin(), eval.end());
	reverse(vec[u].begin(), vec[u].end());
	for (int i = 0; i < (int)vec[u].size(); i++) {
		vector<map<int, int>::iterator> to_del;
		vector<ii> to_add;
		auto [t, val] = vec[u][i];
		M[u][t] += val;
		auto it = M[u].find(t);
		++it;
		int sf = 0;
		while (it != M[u].end()) {
			if (sf + it->second <= val) {
				to_del.pb(it);
				sf += it->second;
			} else {
				to_del.pb(it);
				to_add.eb(it->first, sf + it->second - val);
				break;
			}
			++it;
		}
		for (auto it : to_del) M[u].erase(it);
		for (auto j : to_add) M[u][j.first] += j.second;
	}
	//~ cout << "NODE " << u << '\n';
	//~ for (auto [a, b] : M[u]) cout << a << ' ' << b << '\n';
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 2, p; i <= n; i++) {
		cin >> p;
		adj[p].pb(i);
	}
	for (int i = 1, v, d, w; i <= m; i++) {
		cin >> v >> d >> w;
		mpp[v][d] += w;
	}
	for (int i = 1; i <= n; i++) {
		for (auto j : mpp[i]) vec[i].pb(j);
	}
	dp(1);
	for (auto i : M[1]) ans += i.second;
	cout << ans << '\n';
}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14292 KB Output is correct
6 Correct 8 ms 14292 KB Output is correct
7 Correct 8 ms 14328 KB Output is correct
8 Correct 8 ms 14364 KB Output is correct
9 Correct 10 ms 14364 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 26188 KB Output is correct
2 Correct 50 ms 31164 KB Output is correct
3 Correct 150 ms 49728 KB Output is correct
4 Correct 102 ms 32936 KB Output is correct
5 Correct 143 ms 35832 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14728 KB Output is correct
2 Correct 9 ms 14676 KB Output is correct
3 Correct 10 ms 14648 KB Output is correct
4 Correct 82 ms 50396 KB Output is correct
5 Execution timed out 2087 ms 51576 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 28312 KB Output is correct
2 Correct 105 ms 27696 KB Output is correct
3 Correct 96 ms 35824 KB Output is correct
4 Correct 85 ms 29256 KB Output is correct
5 Correct 71 ms 49464 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14292 KB Output is correct
6 Correct 8 ms 14292 KB Output is correct
7 Correct 8 ms 14328 KB Output is correct
8 Correct 8 ms 14364 KB Output is correct
9 Correct 10 ms 14364 KB Output is correct
10 Correct 115 ms 31180 KB Output is correct
11 Correct 108 ms 30280 KB Output is correct
12 Correct 94 ms 35844 KB Output is correct
13 Correct 88 ms 29248 KB Output is correct
14 Correct 79 ms 49388 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15088 KB Output is correct
2 Correct 34 ms 16468 KB Output is correct
3 Correct 36 ms 16452 KB Output is correct
4 Correct 43 ms 16544 KB Output is correct
5 Correct 16 ms 15572 KB Output is correct
6 Correct 33 ms 20860 KB Output is correct
7 Correct 34 ms 26408 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14292 KB Output is correct
6 Correct 8 ms 14292 KB Output is correct
7 Correct 8 ms 14328 KB Output is correct
8 Correct 8 ms 14364 KB Output is correct
9 Correct 10 ms 14364 KB Output is correct
10 Correct 7 ms 14728 KB Output is correct
11 Correct 9 ms 14676 KB Output is correct
12 Correct 10 ms 14648 KB Output is correct
13 Correct 82 ms 50396 KB Output is correct
14 Execution timed out 2087 ms 51576 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14292 KB Output is correct
6 Correct 8 ms 14292 KB Output is correct
7 Correct 8 ms 14328 KB Output is correct
8 Correct 8 ms 14364 KB Output is correct
9 Correct 10 ms 14364 KB Output is correct
10 Correct 69 ms 26188 KB Output is correct
11 Correct 50 ms 31164 KB Output is correct
12 Correct 150 ms 49728 KB Output is correct
13 Correct 102 ms 32936 KB Output is correct
14 Correct 143 ms 35832 KB Output is correct
15 Correct 7 ms 14728 KB Output is correct
16 Correct 9 ms 14676 KB Output is correct
17 Correct 10 ms 14648 KB Output is correct
18 Correct 82 ms 50396 KB Output is correct
19 Execution timed out 2087 ms 51576 KB Time limit exceeded
20 Halted 0 ms 0 KB -