# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
896791 | math_rabbit_1028 | Magic Tree (CEOI19_magictree) | C++14 | 103 ms | 35500 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, k, par[101010];
pii arr[101010];
vector<int> adj[101010];
map<int, ll> dp[101010];
void solve(int v) {
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i];
solve(u);
if (dp[v].size() < dp[u].size()) swap(dp[v], dp[u]);
for (auto iter = dp[u].begin(); iter != dp[u].end(); iter++) {
dp[v][iter->first] += iter->second;
}
}
dp[v][arr[v].first] += arr[v].second;
auto iter = dp[v].upper_bound(arr[v].first);
while (iter != dp[v].end() && arr[v].second > 0) {
if (iter->second > arr[v].second) {
iter->second -= arr[v].second;
arr[v].second = 0;
}
else {
arr[v].second -= iter->second;
iter = dp[v].erase(iter);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 2; i <= n; i++) {
cin >> par[i];
adj[par[i]].push_back(i);
}
for (int i = 1; i <= m; i++) {
int v, d, w;
cin >> v >> d >> w;
arr[v] = {d, w};
}
solve(1);
ll ans = 0;
for (auto iter = dp[1].begin(); iter != dp[1].end(); iter++) {
ans += iter->second;
}
cout << ans << "\n";
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |