oj.uz

Submission #681075

# Submission time Handle Problem Language Result Execution time Memory
681075 2023-01-12T10:25:47 Z peijar Magic Tree (CEOI19_magictree) C++17
34 / 100
 499 ms 1048576 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommet, nbFruits, nbJours;
  cin >> nbSommet >> nbFruits >> nbJours;
  vector<vector<int>> childs(nbSommet);

  for (int i = 1; i < nbSommet; ++i) {
    int p;
    cin >> p;
    childs[p - 1].push_back(i);
  }
  vector<pair<int, int>> fruits(nbSommet, pair(-1, -1));
  for (int i = 0; i < nbFruits; ++i) {
    int v, d, w;
    cin >> v >> d >> w;
    --v;
    fruits[v] = pair(d - 1, w);
  }
  vector<vector<int>> dp(nbSommet, vector<int>(nbJours));

  for (int u = nbSommet - 1; u >= 0; --u) {
    for (int v : childs[u])
      for (int d = 0; d < nbJours; ++d)
        dp[u][d] += dp[v][d];
    if (fruits[u] == pair<int, int>(-1, -1))
      continue;
    auto [d, w] = fruits[u];
    int x = dp[u][d] + w;
    for (int dd = d; dd < nbJours; ++dd)
      dp[u][dd] = max(dp[u][dd], x);
  }
  cout << dp[0].back() << endl;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 462 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 6 ms 8276 KB Output is correct
3 Correct 5 ms 8264 KB Output is correct
4 Runtime error 499 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 62 ms 13624 KB Output is correct
2 Correct 46 ms 13636 KB Output is correct
3 Correct 44 ms 14284 KB Output is correct
4 Correct 34 ms 12232 KB Output is correct
5 Correct 44 ms 14892 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 72 ms 27144 KB Output is correct
11 Correct 69 ms 19272 KB Output is correct
12 Correct 55 ms 27732 KB Output is correct
13 Correct 49 ms 25616 KB Output is correct
14 Correct 46 ms 28344 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 387 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 5 ms 8276 KB Output is correct
11 Correct 6 ms 8276 KB Output is correct
12 Correct 5 ms 8264 KB Output is correct
13 Runtime error 499 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Runtime error 462 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -