Submission #1221711

#TimeUsernameProblemLanguageResultExecution timeMemory
1221711MateiKing80Magic Tree (CEOI19_magictree)C++20
13 / 100
1490 ms1114112 KiB
#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);
	}
	if (greutate[nod]) {
		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);
			suma += (*it).sc;
			if (suma >= greutate[nod]) {
				baga = {(*it).fr, suma - greutate[nod]};
				break;
			}
			it ++;
		}
		for (auto i : deScos)
			dp[nod].erase(i);
		if (baga != (pii){-1, -1} && baga.sc != 0)
			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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...