oj.uz

Submission #680215

# Submission time Handle Problem Language Result Execution time Memory
680215 2023-01-10T09:28:41 Z flappybird Magic Tree (CEOI19_magictree) C++17
3 / 100
 2000 ms 37132 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 101010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define rev(x) ((x<N*2)?(x+N*2):(x-N*2))
#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif
map<int, ll> mp[MAX];
vector<int> adj[MAX];
int D[MAX];
int W[MAX];
void dfs(int x) {
	for (auto v : adj[x]) {
		dfs(v);
		if (mp[v].size() > mp[x].size()) swap(mp[v], mp[x]);
		for (auto& [t, val] : mp[v]) mp[x][t] += val;
	}
	if (D[x]) {
		mp[x][D[x]] += W[x];
		ll sum = W[x];
		while (sum) {
			auto it = mp[x].upper_bound(D[x]);
			if (it == mp[x].end()) break;
			ll val = it->second;
			ll m = min(sum, val);
			mp[x][it->first] -= m;
			sum -= m;
		}
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, K;
	cin >> N >> M >> K;
	int i, p, a, b;
	for (i = 2; i <= N; i++) cin >> p, adj[p].push_back(i);
	while (M--) {
		cin >> p >> a >> b;
		D[p] = a;
		W[p] = b;
	}
	dfs(1);
	ll ans = 0;
	for (auto& [_, v] : mp[1]) ans += v;
	cout << ans << ln;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7440 KB Output is correct
2 Execution timed out 2070 ms 7448 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 18492 KB Output is correct
2 Correct 41 ms 17764 KB Output is correct
3 Correct 132 ms 37132 KB Output is correct
4 Correct 88 ms 20004 KB Output is correct
5 Correct 109 ms 21496 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 7508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 11864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7440 KB Output is correct
2 Execution timed out 2070 ms 7448 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 8020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7440 KB Output is correct
2 Execution timed out 2070 ms 7448 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7440 KB Output is correct
2 Execution timed out 2070 ms 7448 KB Time limit exceeded
3 Halted 0 ms 0 KB -