Submission #945658

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
945658	2024-03-14T06:05:56 Z	vjudge1	Magic Tree (CEOI19_magictree)	C++17	14 / 100	450 ms	614704 KB

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

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

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.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	7260 KB	Output is correct
2	Correct	16 ms	8256 KB	Output is correct
3	Correct	29 ms	8284 KB	Output is correct
4	Correct	24 ms	8412 KB	Output is correct
5	Correct	30 ms	8512 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	60 ms	14864 KB	Output is correct
5	Correct	60 ms	15048 KB	Output is correct
6	Correct	80 ms	14860 KB	Output is correct

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	450 ms	614704 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 16.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	2640 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 22.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #8
0 / 17.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-