Submission #1221649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221649		MateiKing80	Magic Tree (CEOI19_magictree)	C++20	3 / 100	1449 ms	1114112 KiB

magictree

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

using pii = pair<int, int>;
#define fr first
#define sc second

const int N = 1e5 + 5;

int timp[N], greutate[N];
vector<int> vec[N];
set<pii> dp[N];

void dfs(int nod) {
	for (auto i : vec[nod]) {
		dfs(i);
		if (dp[i].size() > dp[nod].size())
			swap(dp[i], dp[nod]);
		for (auto j : dp[i])
			dp[nod].insert(j);
	}
	vector<pii> deScos;
	pii baga = {-1, -1};
	auto it = dp[nod].lower_bound({timp[nod], -1});
	if (it != dp[nod].end() && (*it).fr == timp[nod]) {
		auto x = *it;
		dp[nod].erase(x);
		x.sc += greutate[nod];
		dp[nod].insert(x);
	}
	else
		dp[nod].insert({timp[nod], greutate[nod]});
	it = dp[nod].lower_bound({timp[nod] + 1, -1});
	int suma = 0;
	while (it != dp[nod].end()) {
		deScos.push_back(*it);
		if (suma + (*it).sc >= greutate[nod]) {
			baga = {(*it).fr, suma + (*it).sc - greutate[nod]};
			break;
		}
	}
	for (auto i : deScos)
		dp[nod].erase(i);
	if (baga != (pii){-1, -1})
		dp[nod].insert(baga);
}

signed main() {
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 2; i <= n; i ++) {
		int p;
		cin >> p;
		vec[p].push_back(i);
	}
	for (int i = 0; i < m; i ++) {
		int v, d, w;
		cin >> v >> d >> w;
		timp[v] = d;
		greutate[v] = w;
	}
	dfs(1);
	int ans = 0;
	for (auto i : dp[1])
		ans += i.sc;
	cout << ans << '\n';
}

• 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