oj.uz

Submission #945611

# Submission time Handle Problem Language Result Execution time Memory
945611 2024-03-14T05:35:25 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
14 / 100
 86 ms 15048 KB 
#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_to[1001], dp_v[1001], cur[1001];
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 <= 1000; ++k) {
      chmax(Max, dp_to[k]);
      cur[k] += Max;
      dp_v[k] += Max;
    }
  }
  if (f[v].second != -1) {
    chmax(dp_v[f[v].second], cur[f[v].second] + f[v].first);
  }
  dp_to[0] = cur[0] = 0;
  for (int k = 1; k <= 1000; ++k) {
    chmax(dp_v[k], dp_v[k - 1]);
    dp_to[k] = cur[k] = 0;
  }
  swap(dp_v, dp_to);
}

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 (m <= 1000) {
    dfs(1);
    cout << *max_element(dp_to, dp_to + 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);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 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 8028 KB Output is correct
3 Correct 28 ms 8428 KB Output is correct
4 Correct 28 ms 8412 KB Output is correct
5 Correct 28 ms 8540 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 60 ms 14876 KB Output is correct
5 Correct 58 ms 15048 KB Output is correct
6 Correct 86 ms 14988 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 3396 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

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