oj.uz

Submission #776206

# Submission time Handle Problem Language Result Execution time Memory
776206 2023-07-07T12:09:43 Z hazzle Magic Tree (CEOI19_magictree) C++17
34 / 100
 763 ms 1048576 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("avx2")

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;

template <typename T>
using prq = priority_queue <T>;

template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;

template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }

inline int solve(){
      int n, m, k;
      cin >> n >> m >> k;
      vec <vec <int>> g(n);
      for (int i = 1; i < n; ++i){
            int p; cin >> p, --p;
            g[p].push_back(i);
      }
      vec <int> d(n), w(n);
      for (int i = 0; i < m; ++i){
            int u, x, y;
            cin >> u >> x >> y, --u;
            d[u] = x, w[u] = y;
      }
      vec <vec <ll>> dp(n, vec <ll> (k + 1));
      auto dfs = [&](auto &&dfs, int u) -> void{
            for (auto &v: g[u]){
                  dfs(dfs, v);
                  for (int i = 1; i <= k; ++i){
                        dp[u][i] += dp[v][i];
                  }
            }
            if (d[u] != 0){
                  ll nw = dp[u][d[u]] + w[u];
                  for (int i = d[u]; i <= k; ++i){
                        umax(dp[u][i], nw);
                  }
            }
      };
      dfs(dfs, 0);
      cout << *max_element(all(dp[0]));
      return 0;
}

inline void precalc(){}

signed main(){
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      int tst = 1; //cin >> tst;
      precalc();
      while(tst--) solve();
      return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 763 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8276 KB Output is correct
2 Correct 5 ms 8276 KB Output is correct
3 Correct 5 ms 8276 KB Output is correct
4 Runtime error 358 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 12620 KB Output is correct
2 Correct 40 ms 12664 KB Output is correct
3 Correct 37 ms 15168 KB Output is correct
4 Correct 27 ms 11064 KB Output is correct
5 Correct 35 ms 18352 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 67 ms 26052 KB Output is correct
11 Correct 50 ms 18124 KB Output is correct
12 Correct 52 ms 28632 KB Output is correct
13 Correct 33 ms 24448 KB Output is correct
14 Correct 42 ms 31768 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 338 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 5 ms 8276 KB Output is correct
11 Correct 5 ms 8276 KB Output is correct
12 Correct 5 ms 8276 KB Output is correct
13 Runtime error 358 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Runtime error 763 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -