Submission #709372

#	Time	Username	Problem	Language	Result	Execution time	Memory
709372		pauloamed	Magic Tree (CEOI19_magictree)	C++14	100 / 100	214 ms	38256 KiB

magictree

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN = 100010;
vector<int> v[MAXN];

int D[MAXN], W[MAXN];

map<int,int> f[MAXN];

void solve(int x) {
  for(auto y : v[x]) {
    solve(y);
    if(f[y].size() > f[x].size()) swap(f[y], f[x]);
    for(auto [t, w] : f[y]) f[x][t] += w;
  }

  if(D[x] == 0) return;

  f[x][D[x]] += W[x];
  int t = D[x];
  int comp = W[x];
  for(auto it = f[x].upper_bound(t); it != f[x].end(); it = f[x].upper_bound(t)) {
    if(it->second <= comp) {
      comp -= it->second;
      f[x].erase(it);
    } else {
      it->second -= comp;
      if(it->second == 0) f[x].erase(it);
      break;
    }
  }
}

int32_t main(){
  int n, m, k; cin >> n >> m >> k;
  for(int i = 1; i < n; ++i) {
    int p; cin >> p; p--;
    v[p].push_back(i);
  }

  for(int i = 0; i < m; ++i) {
    int x; cin >> x; x--;
    cin >> D[x] >> W[x];
  }

  solve(0);

  int ans = 0;
  for(auto [a, b] : f[0]) ans += b;
  cout << ans << "\n";
}

Compilation message (stderr)

magictree.cpp: In function 'void solve(long long int)':
magictree.cpp:16:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for(auto [t, w] : f[y]) f[x][t] += w;
      |              ^
magictree.cpp: In function 'int32_t main()':
magictree.cpp:51:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |   for(auto [a, b] : f[0]) ans += b;
      |            ^

• 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