Submission #467798

#TimeUsernameProblemLanguageResultExecution timeMemory
467798ivan_tudorMagic Tree (CEOI19_magictree)C++14
100 / 100
159 ms36980 KiB
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> sons[N];
map<int, long long> dp[N];
pair<int, int> fruits[N];

void dfs(int nod){
  for(auto x: sons[nod]){
    dfs(x);
    if(dp[x].size() >  dp[nod].size())
      swap(dp[x], dp[nod]);
    for(auto vl : dp[x]){
      dp[nod][vl.first] += vl.second;
    }
  }
  if(fruits[nod].first == 0)
    return;
  long long d = fruits[nod].first, w = fruits[nod].second;
  dp[nod][d] += w;
  auto itr = dp[nod].upper_bound(d);
  while(itr != dp[nod].end() && w > 0){
    long long todel = min((*itr).second, w);
    w -= todel;
    (*itr).second -= todel;
    if((*itr).second == 0){
      itr = dp[nod].erase(itr);
    }
  }

}
int main()
{
  //freopen(".in","r",stdin);
  ios::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;
    sons[p].push_back(i);
  }
  for(int i = 1; i <= m; i++){
    int v, d, w;
    cin>>v>>d>>w;
    fruits[v] = {d, w};
  }
  dfs(1);
  long long ans = 0;
  for(auto x: dp[1])
    ans += x.second;
  cout<<ans;
  return 0;
}
#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...