oj.uz

Submission #725220

# Submission time Handle Problem Language Result Execution time Memory
725220 2023-04-17T03:52:58 Z pavement Magic Tree (CEOI19_magictree) C++17
50 / 100
 2000 ms 53312 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 += val;
			++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 8 ms 14292 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 7 ms 14408 KB Output is correct
4 Correct 8 ms 14308 KB Output is correct
5 Correct 9 ms 14312 KB Output is correct
6 Correct 10 ms 14416 KB Output is correct
7 Correct 8 ms 14400 KB Output is correct
8 Correct 8 ms 14292 KB Output is correct
9 Correct 8 ms 14416 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 26240 KB Output is correct
2 Correct 51 ms 31188 KB Output is correct
3 Correct 156 ms 49748 KB Output is correct
4 Correct 125 ms 32892 KB Output is correct
5 Correct 151 ms 35908 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14676 KB Output is correct
2 Correct 8 ms 14660 KB Output is correct
3 Correct 9 ms 14676 KB Output is correct
4 Correct 79 ms 52324 KB Output is correct
5 Execution timed out 2087 ms 53312 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 28352 KB Output is correct
2 Correct 113 ms 27636 KB Output is correct
3 Correct 88 ms 35880 KB Output is correct
4 Correct 69 ms 29252 KB Output is correct
5 Correct 68 ms 49460 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 7 ms 14408 KB Output is correct
4 Correct 8 ms 14308 KB Output is correct
5 Correct 9 ms 14312 KB Output is correct
6 Correct 10 ms 14416 KB Output is correct
7 Correct 8 ms 14400 KB Output is correct
8 Correct 8 ms 14292 KB Output is correct
9 Correct 8 ms 14416 KB Output is correct
10 Correct 123 ms 32604 KB Output is correct
11 Correct 115 ms 31612 KB Output is correct
12 Correct 93 ms 37412 KB Output is correct
13 Correct 64 ms 30384 KB Output is correct
14 Correct 89 ms 50936 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14976 KB Output is correct
2 Correct 35 ms 17008 KB Output is correct
3 Correct 36 ms 17052 KB Output is correct
4 Correct 35 ms 17044 KB Output is correct
5 Correct 15 ms 15700 KB Output is correct
6 Correct 35 ms 21452 KB Output is correct
7 Correct 40 ms 27000 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 7 ms 14408 KB Output is correct
4 Correct 8 ms 14308 KB Output is correct
5 Correct 9 ms 14312 KB Output is correct
6 Correct 10 ms 14416 KB Output is correct
7 Correct 8 ms 14400 KB Output is correct
8 Correct 8 ms 14292 KB Output is correct
9 Correct 8 ms 14416 KB Output is correct
10 Correct 9 ms 14676 KB Output is correct
11 Correct 8 ms 14660 KB Output is correct
12 Correct 9 ms 14676 KB Output is correct
13 Correct 79 ms 52324 KB Output is correct
14 Execution timed out 2087 ms 53312 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 7 ms 14408 KB Output is correct
4 Correct 8 ms 14308 KB Output is correct
5 Correct 9 ms 14312 KB Output is correct
6 Correct 10 ms 14416 KB Output is correct
7 Correct 8 ms 14400 KB Output is correct
8 Correct 8 ms 14292 KB Output is correct
9 Correct 8 ms 14416 KB Output is correct
10 Correct 67 ms 26240 KB Output is correct
11 Correct 51 ms 31188 KB Output is correct
12 Correct 156 ms 49748 KB Output is correct
13 Correct 125 ms 32892 KB Output is correct
14 Correct 151 ms 35908 KB Output is correct
15 Correct 9 ms 14676 KB Output is correct
16 Correct 8 ms 14660 KB Output is correct
17 Correct 9 ms 14676 KB Output is correct
18 Correct 79 ms 52324 KB Output is correct
19 Execution timed out 2087 ms 53312 KB Time limit exceeded
20 Halted 0 ms 0 KB -