oj.uz

Submission #945584

# Submission time Handle Problem Language Result Execution time Memory
945584 2024-03-14T05:16:50 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
37 / 100
 68 ms 37716 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[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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7260 KB Output is correct
2 Correct 17 ms 8936 KB Output is correct
3 Correct 31 ms 9812 KB Output is correct
4 Correct 26 ms 9332 KB Output is correct
5 Correct 32 ms 10068 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 25428 KB Output is correct
2 Correct 62 ms 25468 KB Output is correct
3 Correct 53 ms 30544 KB Output is correct
4 Correct 39 ms 24576 KB Output is correct
5 Correct 42 ms 37716 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 68 ms 25680 KB Output is correct
11 Correct 57 ms 25624 KB Output is correct
12 Correct 54 ms 30544 KB Output is correct
13 Correct 39 ms 24528 KB Output is correct
14 Correct 43 ms 37716 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Incorrect 1 ms 860 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 19 ms 7260 KB Output is correct
11 Correct 17 ms 8936 KB Output is correct
12 Correct 31 ms 9812 KB Output is correct
13 Correct 26 ms 9332 KB Output is correct
14 Correct 32 ms 10068 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Incorrect 1 ms 860 KB Output isn't correct
17 Halted 0 ms 0 KB -