Submission #467798

#	Time	Username	Problem	Language	Result	Execution time	Memory
467798		ivan_tudor	Magic Tree (CEOI19_magictree)	C++14	100 / 100	159 ms	36980 KiB

magictree

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17