Submission #680215

#	Time	Username	Problem	Language	Result	Execution time	Memory
680215		flappybird	Magic Tree (CEOI19_magictree)	C++17	3 / 100	2075 ms	37132 KiB

magictree

#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
• Subtask 2: 3 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17