Submission #945584

#	Time	Username	Problem	Language	Result	Execution time	Memory
945584		vjudge1	Magic Tree (CEOI19_magictree)	C++17	37 / 100	68 ms	37716 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
  return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
  return a < b ? (a = b) == b : false;
}

void compress(vector<int>& a) {
  vector<int> v;
  map<int, int> mp;
  for (int i = 1; i < size(a); ++i) {
    if (mp.count(a[i])) continue;
    v.push_back(a[i]);
    mp[a[i]];
  }
  sort(all(v));
  for (int i = 0; i < size(v); ++i) {
    mp[v[i]] = i + 1;
  }
  for (int i = 1; i < size(a); ++i) {
    a[i] = mp[a[i]];
  }
}

const int N = 1e5 + 1;

int dp[N][21];
vector<vector<int>> g;
vector<pair<int, int>> f;

void dfs(int v) {
  for (int to : g[v]) {
    dfs(to);
    int Max = 0;
    for (int k = 0; k <= 20; ++k) {
      chmax(Max, dp[to][k]);
      dp[v][k] += Max;
    }
  }
  if (f[v].second != -1) {
    int cur = 0;
    for (int to : g[v]) {
      cur += dp[to][f[v].second];
    }
    chmax(dp[v][f[v].second], cur + f[v].first);
  }
  for (int k = 1; k <= 20; ++k) {
    chmax(dp[v][k], dp[v][k - 1]);
  }
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m, k;
  cin >> n >> m >> k;
  int p[n + 1];
  p[1] = -1;
  vector<int> u(m + 1), d(m + 1), w(m + 1);
  g.resize(n + 1);
  f.assign(n + 1, {-1, -1});
  for (int i = 2; i <= n; ++i) {
    cin >> p[i];
    g[p[i]].push_back(i);
  }
  bool flag = true;
  for (int i = 1; i <= m; ++i) {
    cin >> u[i] >> d[i] >> w[i];
    if (!g[u[i]].empty()) flag = false;
  }
  if (flag) {
    cout << accumulate(w.begin() + 1, w.end(), 0ll);
    return 0;
  }
  compress(d);
  for (int i = 1; i <= m; ++i) {
    f[u[i]] = {w[i], d[i]};
  }
  dfs(1);
  cout << *max_element(dp[1], dp[1] + k + 1);
}

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