oj.uz

Submission #443100

# Submission time Handle Problem Language Result Execution time Memory
443100 2021-07-09T16:20:23 Z ltf0501 Dungeons Game (IOI21_dungeons) C++17
11 / 100
 7000 ms 218852 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
 
const int kN = 4e5 + 10;
const int kC = 25;
// subtask 3
int n;
vector<int> s, p, w, l;
long long suf[kN];
int climb[kC][kN], MAX;
long long max_pow[kC][kN], gained_pow[kC][kN];
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
  n = _n, s = _s, p = _p, w = _w, l = _l;
  
  for(int i = n - 1; i >= 0; i--) suf[i] = s[i] + suf[w[i]], MAX = max(MAX, s[i]);
  for(int i = 0; i < n; i++) {
    climb[0][i] = l[i];
    max_pow[0][i] = s[i] - 1;
    gained_pow[0][i] = p[i];
  }
  climb[0][n] = n;
 
  for(int j = 1; j < kC; j++) {
    for(int i = 0; i < n; i++) {
      climb[j][i] = climb[j - 1][climb[j - 1][i]];
      max_pow[j][i] = min(max_pow[j - 1][i], max_pow[j - 1][climb[j - 1][i]] - gained_pow[j - 1][i]);
      gained_pow[j][i] = gained_pow[j - 1][i] + gained_pow[j - 1][climb[j - 1][i]];
    }
  }
	return;
}
 
long long simulate(int x, int z) {
  long long res = z;
  int cnt = 0;
  while(x < n && res < int(1e7)) {
    for(int j = kC - 1; j >= 0; j--) {
      if(res > max_pow[j][x]) continue;
      res += gained_pow[j][x], x = climb[j][x];
    }
    cnt++;
    if(x == n) break;
    res += s[x], x = w[x];
  }
  res += suf[x];
  return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 3 ms 1868 KB Output is correct
4 Correct 41 ms 27976 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 40 ms 28064 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Execution timed out 7093 ms 218852 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 101 ms 28752 KB Output is correct
3 Correct 86 ms 28788 KB Output is correct
4 Execution timed out 7093 ms 28796 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 101 ms 28752 KB Output is correct
3 Correct 86 ms 28788 KB Output is correct
4 Execution timed out 7093 ms 28796 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 101 ms 28752 KB Output is correct
3 Correct 86 ms 28788 KB Output is correct
4 Execution timed out 7093 ms 28796 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Execution timed out 7093 ms 218852 KB Time limit exceeded
3 Halted 0 ms 0 KB -