Submission #825185

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
825185	2023-08-14T15:17:39 Z	NK_	Magic Tree (CEOI19_magictree)	C++17	47 / 100	2000 ms	29704 KB

magictree

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using ll = long long;
using vl = V<ll>;

using T = map<int, ll>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M, K; cin >> N >> M >> K;

	V<vi> chd(N); for(int u = 1; u < N; u++) {
		int p; cin >> p; --p;
		chd[p].pb(u);
	}

	vi W(N, 0), D(N, -1);

	for(int i = 0; i < M; i++) {
		int v, d, w; cin >> v >> d >> w; --v, --d;
		D[v] = d, W[v] = w;
	}
	
	function<T(int)> dfs = [&](int u) {
		T R;
		for(auto& v : chd[u]) {
			T r = dfs(v);
			for(auto p : r) R[p.first] += p.second;
		}		

		if (D[u] != -1) {
			R[D[u]] += W[u];
			ll amt = 0;
			while(1) {
				auto it = R.upper_bound(D[u]);
				if (it == end(R)) break;

				amt += it->s;
				if (W[u] < amt) { it->s = amt - W[u]; break; }
				else R.erase(it);
			}
		}

		return R;
	};

	T ans = dfs(0);
	ll ANS = 0;
	for(auto p : ans) ANS += p.second;
	cout << ANS << nl;
    return 0;
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	324 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct

Subtask #2
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	7900 KB	Output is correct
2	Execution timed out	2068 ms	15720 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	2 ms	584 KB	Output is correct
3	Correct	9 ms	580 KB	Output is correct
4	Correct	59 ms	28832 KB	Output is correct
5	Execution timed out	2078 ms	29704 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	7180 KB	Output is correct
2	Correct	37 ms	7124 KB	Output is correct
3	Correct	40 ms	16232 KB	Output is correct
4	Correct	26 ms	5636 KB	Output is correct
5	Correct	48 ms	28964 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	324 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	43 ms	6476 KB	Output is correct
11	Correct	40 ms	6404 KB	Output is correct
12	Correct	111 ms	15536 KB	Output is correct
13	Correct	24 ms	5000 KB	Output is correct
14	Correct	103 ms	28332 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1332 KB	Output is correct
2	Correct	16 ms	5684 KB	Output is correct
3	Correct	16 ms	5716 KB	Output is correct
4	Correct	18 ms	5716 KB	Output is correct
5	Correct	8 ms	4164 KB	Output is correct
6	Correct	193 ms	9496 KB	Output is correct
7	Correct	203 ms	14832 KB	Output is correct

Subtask #7
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	324 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	2 ms	584 KB	Output is correct
12	Correct	9 ms	580 KB	Output is correct
13	Correct	59 ms	28832 KB	Output is correct
14	Execution timed out	2078 ms	29704 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #8
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	324 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	45 ms	7900 KB	Output is correct
11	Execution timed out	2068 ms	15720 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Submission #825185

Compilation message