Submission #1083444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083444		vjudge1	Magic Tree (CEOI19_magictree)	C++17	100 / 100	81 ms	34616 KiB

magictree

#include <bits/stdc++.h>


#define                int  long long
#define                pii  pair<int, int>
#define                 fi  first
#define                 se  second
#define                 ld  long double
#define                 vi  vector<int>
#define                vii  vector<vector<int>>
#define             all(v)  (v).begin(), (v).end()
#define       rep(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define       per(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)

using namespace std;

const int MOD = 1e9 + 7;

int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}

int mul(int a, int b) {
  (a *= b) %= MOD;
  return a;
}

int bin_pow(int x, int y) {
  int res=1;
  while(y){if(y&1)res=res*x%MOD;x=x*x%MOD;y>>=1;}
  return res;
}

const int INF = 1e17;
const int maxn = 1e5 + 5;

int N, M, K;
int day[maxn + 5], weight[maxn + 5];
map<int, int> f[maxn + 5];
vector<int> g[maxn + 5];

void dfs(int u) {
  for (int v : g[u]) {
    dfs(v);
    if (f[v].size() > f[u].size()) swap(f[v], f[u]);
    for (auto it : f[v]) f[u][it.first] += it.second;
    f[v].clear();
  }
  if (day[u] && weight[u]) {
    int s = 0;
    while (true) {
      auto it = f[u].upper_bound(day[u]);
      if (it == f[u].end()) break;
      if (it->second + s <= weight[u]) {
        s += it->second;
        f[u].erase(it);
      } else {
        it->second += s - weight[u];
        break;
      }
    }
    f[u][day[u]] += weight[u];
  }
}

void solve(int tc) {
  // trong 1 subtree, neu chon dinh thi nhung dinh a[v] > a[u] ko chon
  // con ko chon dinh u thi chon cac dinh a[v] > a[u]
  
  cin >> N >> M >> K;
  rep(i, 2, N) {
    int p; cin >> p;
    g[p].push_back(i);
  }
  rep(i, 1, M) {
    int v, d, w; cin >> v >> d >> w;
    day[v] = d;
    weight[v] = w;
  }
  dfs(1);
  int ans = 0;
  for (auto it : f[1]) {
    ans += it.second;
  }
  cout << ans << '\n';
}

signed main() {

  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; ++i) {
    solve(i);
  }
}

• 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