Submission #945659

#	Time	Username	Problem	Language	Result	Execution time	Memory
945659		vjudge1	Magic Tree (CEOI19_magictree)	C++17	14 / 100	441 ms	621908 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][1001];
vector<vector<int>> g;
vector<pair<int, int>> f;

void dfs(int v) {
  int cur = 0;
  for (int to : g[v]) {
    dfs(to);
    int Max = 0;
    for (int k = 0; k <= 1001; ++k) {
      chmax(Max, dp[to][k]);
      if (k == f[v].second) cur += Max;
      dp[v][k] += Max;
    }
  }
  if (f[v].second != -1) {
    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]);
  }
}

struct fenwick {
  int n;
  vector<int> t;
  fenwick(int n) {
    this -> n = n;
    t.assign(n + 1, 0);
  }
  void upd(int i, int delta) {
    for (; i <= n; i += i & -i) {
      chmax(t[i], delta);
    }
  }
  int get(int i) {
    int res = 0;
    for (; i > 0; i -= i & -i) {
      chmax(res, t[i]);
    }
    return res;
  }
};

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]};
  }
  if (k <= 20) {
    dfs(1);
    cout << *max_element(dp[1], dp[1] + k + 1);
    return 0;
  }
  fenwick fenw(k);
  for (int i = n; i >= 1; --i) {
    if (f[i].second != -1) {
      fenw.upd(f[i].second, fenw.get(f[i].second) + f[i].first);
    }
  }
  cout << fenw.get(k);
}

Compilation message (stderr)

magictree.cpp: In function 'void dfs(long long int)':
magictree.cpp:47:16: warning: iteration 1001 invokes undefined behavior [-Waggressive-loop-optimizations]
   47 |       dp[v][k] += Max;
      |       ~~~~~~~~~^~~~~~
magictree.cpp:44:23: note: within this loop
   44 |     for (int k = 0; k <= 1001; ++k) {
      |                     ~~^~~~~~~

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