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;
const int MAXN = 1e5;
struct Tree{
vector<int> adj[MAXN + 1];
int ds[MAXN + 1], js[MAXN + 1];
void insert(map<int, long long>* dp, int v){
(*dp)[ds[v]] += js[v];
auto ptr = dp->find(ds[v]);
int j_left = js[v];
while(j_left > 0 && next(ptr) != dp->end()){
auto nxt_ptr = next(ptr);
if(nxt_ptr->second > j_left){
nxt_ptr->second -= j_left;
break;
}
else{
j_left -= nxt_ptr->second;
dp->erase(nxt_ptr);
}
}
}
map<int, long long>* TreeDp(int v){
auto curr_map = new map<int, long long>();
for(auto u : adj[v]){
auto new_map = TreeDp(u);
if(new_map->size() > curr_map->size()) swap(curr_map, new_map);
for(auto [key, value] : *new_map){
(*curr_map)[key] += value;
}
}
if(ds[v] > 0) insert(curr_map, v);
return curr_map;
}
};
Tree T;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N, M, K;
cin>> N>> M>> K;
for(int i=2; i<=N; i++){
int p; cin>> p;
T.adj[p].push_back(i);
}
for(int i=0; i<M; i++){
int v; cin>> v;
cin>> T.ds[v]>> T.js[v];
}
auto dp = T.TreeDp(1);
long long res = 0;
for(auto [key, value] : *dp){
res += value;
}
cout<< res;
return 0;
}
# | 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... |