oj.uz

Submission #812021

# Submission time Handle Problem Language Result Execution time Memory
812021 2023-08-07T06:49:25 Z WLZ Dungeons Game (IOI21_dungeons) C++17
63 / 100
 6815 ms 2097152 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

const int INF = 0x3f3f3f3f;
const ll LINF = 1e18;
const int b = 2;
const int max_log = 24;

int n;
vector< vector<vi> > up; // [k][u][i]: 2^i steps from u, strength [2 ^ k, 2 ^ (k + 1))
vector< vector<vll> > gain, to_win;
vi s, p, w, l;

void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
  n = N; s = S; p = P; w = W; l = L;
  s.push_back(0); p.push_back(0); w.push_back(n); l.push_back(n);
  up.assign(max_log + 2, vector<vi>(n + 1, vi(max_log + 1)));
  gain.assign(max_log + 2, vector<vll>(n + 1, vll(max_log + 1)));
  to_win.assign(max_log + 2, vector<vll>(n + 1, vll(max_log + 1)));
  ll pw = 1;
  for (int k = 0; k <= max_log + 1; k++, pw *= b) {
    if (k == max_log + 1) pw = (ll) 1e8;
    for (int u = 0; u <= n; u++) {
      up[k][u][0] = (s[u] < pw ? w[u] : l[u]);
      gain[k][u][0] = (s[u] < pw ? s[u] : p[u]);
      to_win[k][u][0] = (pw <= s[u] && s[u] < pw * b ? s[u] : LINF);
    }
    for (int i = 1; i <= max_log; i++) {
      for (int u = 0; u <= n; u++) {
        up[k][u][i] = up[k][up[k][u][i - 1]][i - 1];
        gain[k][u][i] = gain[k][u][i - 1] + gain[k][up[k][u][i - 1]][i - 1];
        to_win[k][u][i] = min(to_win[k][u][i - 1], to_win[k][up[k][u][i - 1]][i - 1] - gain[k][u][i - 1]);
      }
    }
  }
}

long long simulate(int x, int z) {
  ll ans = z, pw = 1;
  int k = 0, u = x;
  while (pw * b <= z) pw *= b, k++;
  while (u != n) {
    //while (u != n && ans < pw * b) {
      for (int i = max_log; i >= 0; i--) {
        if (ans + gain[k][u][i] < pw * b && ans < to_win[k][u][i]) {
          ans += gain[k][u][i];
          u = up[k][u][i];
        }
      }
      if (ans < s[u]) ans += p[u], u = l[u];
      else ans += s[u], u = w[u];
    //}
    pw *= b;
    if (++k == max_log + 1) pw = LINF;
  }
  return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 29 ms 31316 KB Output is correct
4 Correct 1283 ms 777236 KB Output is correct
5 Correct 31 ms 31316 KB Output is correct
6 Correct 1277 ms 777232 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15828 KB Output is correct
2 Runtime error 1455 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15924 KB Output is correct
2 Correct 1678 ms 779664 KB Output is correct
3 Correct 1424 ms 779772 KB Output is correct
4 Correct 1334 ms 778096 KB Output is correct
5 Correct 1353 ms 778140 KB Output is correct
6 Correct 1969 ms 778000 KB Output is correct
7 Correct 1978 ms 777896 KB Output is correct
8 Correct 2059 ms 778028 KB Output is correct
9 Correct 1376 ms 778008 KB Output is correct
10 Correct 1925 ms 778028 KB Output is correct
11 Correct 3248 ms 778052 KB Output is correct
12 Correct 6815 ms 778004 KB Output is correct
13 Correct 5800 ms 779276 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15924 KB Output is correct
2 Correct 1678 ms 779664 KB Output is correct
3 Correct 1424 ms 779772 KB Output is correct
4 Correct 1334 ms 778096 KB Output is correct
5 Correct 1353 ms 778140 KB Output is correct
6 Correct 1969 ms 778000 KB Output is correct
7 Correct 1978 ms 777896 KB Output is correct
8 Correct 2059 ms 778028 KB Output is correct
9 Correct 1376 ms 778008 KB Output is correct
10 Correct 1925 ms 778028 KB Output is correct
11 Correct 3248 ms 778052 KB Output is correct
12 Correct 6815 ms 778004 KB Output is correct
13 Correct 5800 ms 779276 KB Output is correct
14 Correct 17 ms 15928 KB Output is correct
15 Correct 1413 ms 779396 KB Output is correct
16 Correct 1546 ms 779652 KB Output is correct
17 Correct 1569 ms 779128 KB Output is correct
18 Correct 1527 ms 779172 KB Output is correct
19 Correct 1945 ms 779280 KB Output is correct
20 Correct 1824 ms 778960 KB Output is correct
21 Correct 2079 ms 779144 KB Output is correct
22 Correct 2392 ms 779140 KB Output is correct
23 Correct 4086 ms 779280 KB Output is correct
24 Correct 4110 ms 779196 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15924 KB Output is correct
2 Correct 1678 ms 779664 KB Output is correct
3 Correct 1424 ms 779772 KB Output is correct
4 Correct 1334 ms 778096 KB Output is correct
5 Correct 1353 ms 778140 KB Output is correct
6 Correct 1969 ms 778000 KB Output is correct
7 Correct 1978 ms 777896 KB Output is correct
8 Correct 2059 ms 778028 KB Output is correct
9 Correct 1376 ms 778008 KB Output is correct
10 Correct 1925 ms 778028 KB Output is correct
11 Correct 3248 ms 778052 KB Output is correct
12 Correct 6815 ms 778004 KB Output is correct
13 Correct 5800 ms 779276 KB Output is correct
14 Correct 17 ms 15928 KB Output is correct
15 Correct 1413 ms 779396 KB Output is correct
16 Correct 1546 ms 779652 KB Output is correct
17 Correct 1569 ms 779128 KB Output is correct
18 Correct 1527 ms 779172 KB Output is correct
19 Correct 1945 ms 779280 KB Output is correct
20 Correct 1824 ms 778960 KB Output is correct
21 Correct 2079 ms 779144 KB Output is correct
22 Correct 2392 ms 779140 KB Output is correct
23 Correct 4086 ms 779280 KB Output is correct
24 Correct 4110 ms 779196 KB Output is correct
25 Correct 1523 ms 778484 KB Output is correct
26 Correct 1645 ms 779616 KB Output is correct
27 Correct 1445 ms 779024 KB Output is correct
28 Correct 1509 ms 779132 KB Output is correct
29 Correct 1691 ms 779528 KB Output is correct
30 Correct 2151 ms 779276 KB Output is correct
31 Correct 2422 ms 779012 KB Output is correct
32 Correct 3575 ms 779148 KB Output is correct
33 Correct 2423 ms 778988 KB Output is correct
34 Correct 3480 ms 778792 KB Output is correct
35 Correct 2656 ms 779148 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15828 KB Output is correct
2 Runtime error 1455 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -