oj.uz

Submission #990947

# Submission time Handle Problem Language Result Execution time Memory
990947 2024-05-31T20:49:59 Z AdamGS Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1867428 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=4e5+7, LG=24, LG2=15, INF=1e9+7;
int nxt[LIM][LG][LG2], sum[LIM][LG][LG2], ile[LIM][LG][LG2];
ll nxt2[LIM][LG], sum2[LIM][LG], S[LIM], P[LIM], W[LIM], L[LIM], n;
void init(int _n, vector<int>_s, vector<int>_p, vector<int>_w, vector<int>_l) {
  n=_n;
  rep(i, n) {
    S[i]=_s[i];
    P[i]=_p[i];
    W[i]=_w[i];
    L[i]=_l[i];
  }
  rep(i, LG) {
    nxt[n][i][0]=n;
    rep(j, n) {
      if(S[j]>=(1<<i)) {
        nxt[j][i][0]=L[j];
        sum[j][i][0]=P[j];
        ile[j][i][0]=min(S[j], (1<<(i+1))-P[j]);
      } else {
        nxt[j][i][0]=W[j];
        sum[j][i][0]=S[j];
        ile[j][i][0]=(1<<(i+1))-S[j];
      }
    }
    for(int l=1; l<LG2; ++l) {
      rep(j, n+1) {
        if(nxt[j][i][l-1]==n) {
          nxt[j][i][l]=nxt[j][i][l-1];
          sum[j][i][l]=sum[j][i][l-1];
          ile[j][i][l]=ile[j][i][l-1];
          continue;
        }
        int a=nxt[j][i][l-1], b=nxt[a][i][l-1];
        nxt[j][i][l]=nxt[b][i][l-1];
        sum[j][i][l]=sum[j][i][l-1]+sum[a][i][l-1]+sum[b][i][l-1];
        ile[j][i][l]=min(ile[j][i][l-1], min(ile[a][i][l-1]-sum[j][i][l-1], ile[b][i][l-1]-sum[j][i][l-1]-sum[a][i][l-1]));
        sum[j][i][l]=min(sum[j][i][l], INF);
        ile[j][i][l]=max(ile[j][i][l], 0);
      }
    }
  }
  nxt2[n][0]=n;
  rep(i, n) {
    nxt2[i][0]=W[i];
    sum2[i][0]=S[i];
  }
  for(int j=1; j<LG; ++j) {
    rep(i, n+1) {
      nxt2[i][j]=nxt2[nxt2[i][j-1]][j-1];
      sum2[i][j]=sum2[nxt2[i][j-1]][j-1]+sum2[i][j-1];
    }
  }
  return;
}
ll simulate(int x, int _z) {
  ll z=_z;
  rep(i, LG) if(z<(1ll<<(ll)(i+1))) {
    for(int j=LG2-1; j>=0; --j) if(ile[x][i][j]>z) {
      z+=sum[x][i][j];
      x=nxt[x][i][j];
      if(ile[x][i][j]>z) {
        z+=sum[x][i][j];
        x=nxt[x][i][j];
      }
    }
    if(x==n) return z;
    if(z>=S[x]) {
      z+=S[x];
      x=W[x];
    } else {
      z+=P[x];
      x=L[x];
    }
    if(x==n) return z;
  }
  for(int i=LG-1; i>=0; --i) if(nxt2[x][i]<n) {
    z+=sum2[x][i];
    x=nxt2[x][i];
  }
  z+=sum2[x][0];
  x=nxt2[x][0];
  return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 6 ms 25144 KB Output is correct
4 Correct 172 ms 252472 KB Output is correct
5 Correct 7 ms 24924 KB Output is correct
6 Correct 174 ms 252340 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 4270 ms 1867356 KB Output is correct
3 Correct 3919 ms 1867356 KB Output is correct
4 Correct 3686 ms 1867352 KB Output is correct
5 Correct 3080 ms 1867356 KB Output is correct
6 Correct 4704 ms 1867364 KB Output is correct
7 Correct 4255 ms 1867428 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 226 ms 253260 KB Output is correct
3 Correct 203 ms 253268 KB Output is correct
4 Correct 210 ms 253264 KB Output is correct
5 Correct 197 ms 253264 KB Output is correct
6 Correct 270 ms 253264 KB Output is correct
7 Correct 261 ms 253264 KB Output is correct
8 Correct 392 ms 253260 KB Output is correct
9 Correct 176 ms 253264 KB Output is correct
10 Correct 366 ms 253264 KB Output is correct
11 Correct 322 ms 253268 KB Output is correct
12 Correct 1193 ms 253172 KB Output is correct
13 Correct 1207 ms 253136 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 226 ms 253260 KB Output is correct
3 Correct 203 ms 253268 KB Output is correct
4 Correct 210 ms 253264 KB Output is correct
5 Correct 197 ms 253264 KB Output is correct
6 Correct 270 ms 253264 KB Output is correct
7 Correct 261 ms 253264 KB Output is correct
8 Correct 392 ms 253260 KB Output is correct
9 Correct 176 ms 253264 KB Output is correct
10 Correct 366 ms 253264 KB Output is correct
11 Correct 322 ms 253268 KB Output is correct
12 Correct 1193 ms 253172 KB Output is correct
13 Correct 1207 ms 253136 KB Output is correct
14 Correct 5 ms 20828 KB Output is correct
15 Correct 205 ms 253260 KB Output is correct
16 Correct 246 ms 253256 KB Output is correct
17 Correct 239 ms 253264 KB Output is correct
18 Correct 258 ms 253260 KB Output is correct
19 Correct 281 ms 253264 KB Output is correct
20 Correct 362 ms 253052 KB Output is correct
21 Correct 421 ms 253264 KB Output is correct
22 Correct 426 ms 253268 KB Output is correct
23 Correct 617 ms 253268 KB Output is correct
24 Correct 743 ms 253268 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 226 ms 253260 KB Output is correct
3 Correct 203 ms 253268 KB Output is correct
4 Correct 210 ms 253264 KB Output is correct
5 Correct 197 ms 253264 KB Output is correct
6 Correct 270 ms 253264 KB Output is correct
7 Correct 261 ms 253264 KB Output is correct
8 Correct 392 ms 253260 KB Output is correct
9 Correct 176 ms 253264 KB Output is correct
10 Correct 366 ms 253264 KB Output is correct
11 Correct 322 ms 253268 KB Output is correct
12 Correct 1193 ms 253172 KB Output is correct
13 Correct 1207 ms 253136 KB Output is correct
14 Correct 5 ms 20828 KB Output is correct
15 Correct 205 ms 253260 KB Output is correct
16 Correct 246 ms 253256 KB Output is correct
17 Correct 239 ms 253264 KB Output is correct
18 Correct 258 ms 253260 KB Output is correct
19 Correct 281 ms 253264 KB Output is correct
20 Correct 362 ms 253052 KB Output is correct
21 Correct 421 ms 253264 KB Output is correct
22 Correct 426 ms 253268 KB Output is correct
23 Correct 617 ms 253268 KB Output is correct
24 Correct 743 ms 253268 KB Output is correct
25 Correct 200 ms 252488 KB Output is correct
26 Correct 217 ms 253264 KB Output is correct
27 Correct 195 ms 253264 KB Output is correct
28 Correct 214 ms 253260 KB Output is correct
29 Correct 227 ms 253264 KB Output is correct
30 Correct 432 ms 253264 KB Output is correct
31 Correct 515 ms 253268 KB Output is correct
32 Correct 465 ms 253268 KB Output is correct
33 Correct 290 ms 253260 KB Output is correct
34 Correct 342 ms 253260 KB Output is correct
35 Correct 343 ms 253256 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 4270 ms 1867356 KB Output is correct
3 Correct 3919 ms 1867356 KB Output is correct
4 Correct 3686 ms 1867352 KB Output is correct
5 Correct 3080 ms 1867356 KB Output is correct
6 Correct 4704 ms 1867364 KB Output is correct
7 Correct 4255 ms 1867428 KB Output is correct
8 Correct 5 ms 20828 KB Output is correct
9 Correct 226 ms 253260 KB Output is correct
10 Correct 203 ms 253268 KB Output is correct
11 Correct 210 ms 253264 KB Output is correct
12 Correct 197 ms 253264 KB Output is correct
13 Correct 270 ms 253264 KB Output is correct
14 Correct 261 ms 253264 KB Output is correct
15 Correct 392 ms 253260 KB Output is correct
16 Correct 176 ms 253264 KB Output is correct
17 Correct 366 ms 253264 KB Output is correct
18 Correct 322 ms 253268 KB Output is correct
19 Correct 1193 ms 253172 KB Output is correct
20 Correct 1207 ms 253136 KB Output is correct
21 Correct 5 ms 20828 KB Output is correct
22 Correct 205 ms 253260 KB Output is correct
23 Correct 246 ms 253256 KB Output is correct
24 Correct 239 ms 253264 KB Output is correct
25 Correct 258 ms 253260 KB Output is correct
26 Correct 281 ms 253264 KB Output is correct
27 Correct 362 ms 253052 KB Output is correct
28 Correct 421 ms 253264 KB Output is correct
29 Correct 426 ms 253268 KB Output is correct
30 Correct 617 ms 253268 KB Output is correct
31 Correct 743 ms 253268 KB Output is correct
32 Correct 200 ms 252488 KB Output is correct
33 Correct 217 ms 253264 KB Output is correct
34 Correct 195 ms 253264 KB Output is correct
35 Correct 214 ms 253260 KB Output is correct
36 Correct 227 ms 253264 KB Output is correct
37 Correct 432 ms 253264 KB Output is correct
38 Correct 515 ms 253268 KB Output is correct
39 Correct 465 ms 253268 KB Output is correct
40 Correct 290 ms 253260 KB Output is correct
41 Correct 342 ms 253260 KB Output is correct
42 Correct 343 ms 253256 KB Output is correct
43 Correct 2 ms 16728 KB Output is correct
44 Correct 5 ms 20824 KB Output is correct
45 Correct 4103 ms 1867340 KB Output is correct
46 Correct 3276 ms 1867344 KB Output is correct
47 Correct 3507 ms 1867356 KB Output is correct
48 Correct 3239 ms 1867360 KB Output is correct
49 Correct 4261 ms 1867348 KB Output is correct
50 Correct 4601 ms 1867344 KB Output is correct
51 Correct 3269 ms 1867352 KB Output is correct
52 Correct 4598 ms 1867340 KB Output is correct
53 Execution timed out 7130 ms 1719568 KB Time limit exceeded
54 Halted 0 ms 0 KB -