oj.uz

Submission #990959

# Submission time Handle Problem Language Result Execution time Memory
990959 2024-05-31T21:00:08 Z AdamGS Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4757 ms 1877344 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][LG2][LG], sum[LIM][LG2][LG], ile[LIM][LG2][LG], pot[LG2+1];
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) {
  pot[0]=1;
  rep(i, LG2) pot[i+1]=pot[i]*3;
  n=_n;
  rep(i, n) {
    S[i]=_s[i];
    P[i]=_p[i];
    W[i]=_w[i];
    L[i]=_l[i];
  }
  rep(i, LG2) {
    nxt[n][i][0]=n;
    rep(j, n) {
      if(S[j]>=pot[i]) {
        nxt[j][i][0]=L[j];
        sum[j][i][0]=P[j];
        ile[j][i][0]=min(S[j], pot[i+1]-P[j]);
      } else {
        nxt[j][i][0]=W[j];
        sum[j][i][0]=S[j];
        ile[j][i][0]=pot[i+1]-S[j];
      }
    }
    for(int l=1; l<LG; ++l) {
      rep(j, n+1) {
        nxt[j][i][l]=nxt[nxt[j][i][l-1]][i][l-1];
        sum[j][i][l]=sum[j][i][l-1]+sum[nxt[j][i][l-1]][i][l-1];
        ile[j][i][l]=min(ile[j][i][l-1], ile[nxt[j][i][l-1]][i][l-1]-sum[j][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;
  int i=0;
  while(true) {
    while(i<LG2 && pot[i+1]<=z) ++i;
    if(i==LG2) break;
    for(int j=LG-1; j>=0; --j) if(nxt[x][i][j]<n && ile[x][i][j]>z) {
      z+=sum[x][i][j];
      x=nxt[x][i][j];
    }
    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 7 ms 25136 KB Output is correct
4 Correct 175 ms 252476 KB Output is correct
5 Correct 7 ms 24924 KB Output is correct
6 Correct 173 ms 252404 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20824 KB Output is correct
2 Correct 4074 ms 1867356 KB Output is correct
3 Correct 3449 ms 1873320 KB Output is correct
4 Correct 3300 ms 1874788 KB Output is correct
5 Correct 2920 ms 1874780 KB Output is correct
6 Correct 3945 ms 1873420 KB Output is correct
7 Correct 3790 ms 1871784 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 220 ms 254916 KB Output is correct
3 Correct 207 ms 255040 KB Output is correct
4 Correct 200 ms 254288 KB Output is correct
5 Correct 210 ms 254272 KB Output is correct
6 Correct 230 ms 254548 KB Output is correct
7 Correct 237 ms 254544 KB Output is correct
8 Correct 315 ms 254160 KB Output is correct
9 Correct 201 ms 254292 KB Output is correct
10 Correct 285 ms 254032 KB Output is correct
11 Correct 262 ms 254544 KB Output is correct
12 Correct 745 ms 254548 KB Output is correct
13 Correct 766 ms 254548 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 220 ms 254916 KB Output is correct
3 Correct 207 ms 255040 KB Output is correct
4 Correct 200 ms 254288 KB Output is correct
5 Correct 210 ms 254272 KB Output is correct
6 Correct 230 ms 254548 KB Output is correct
7 Correct 237 ms 254544 KB Output is correct
8 Correct 315 ms 254160 KB Output is correct
9 Correct 201 ms 254292 KB Output is correct
10 Correct 285 ms 254032 KB Output is correct
11 Correct 262 ms 254544 KB Output is correct
12 Correct 745 ms 254548 KB Output is correct
13 Correct 766 ms 254548 KB Output is correct
14 Correct 5 ms 20824 KB Output is correct
15 Correct 200 ms 254788 KB Output is correct
16 Correct 216 ms 254800 KB Output is correct
17 Correct 221 ms 254272 KB Output is correct
18 Correct 224 ms 254396 KB Output is correct
19 Correct 244 ms 254548 KB Output is correct
20 Correct 285 ms 254252 KB Output is correct
21 Correct 314 ms 254536 KB Output is correct
22 Correct 350 ms 254292 KB Output is correct
23 Correct 423 ms 254540 KB Output is correct
24 Correct 507 ms 254548 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 220 ms 254916 KB Output is correct
3 Correct 207 ms 255040 KB Output is correct
4 Correct 200 ms 254288 KB Output is correct
5 Correct 210 ms 254272 KB Output is correct
6 Correct 230 ms 254548 KB Output is correct
7 Correct 237 ms 254544 KB Output is correct
8 Correct 315 ms 254160 KB Output is correct
9 Correct 201 ms 254292 KB Output is correct
10 Correct 285 ms 254032 KB Output is correct
11 Correct 262 ms 254544 KB Output is correct
12 Correct 745 ms 254548 KB Output is correct
13 Correct 766 ms 254548 KB Output is correct
14 Correct 5 ms 20824 KB Output is correct
15 Correct 200 ms 254788 KB Output is correct
16 Correct 216 ms 254800 KB Output is correct
17 Correct 221 ms 254272 KB Output is correct
18 Correct 224 ms 254396 KB Output is correct
19 Correct 244 ms 254548 KB Output is correct
20 Correct 285 ms 254252 KB Output is correct
21 Correct 314 ms 254536 KB Output is correct
22 Correct 350 ms 254292 KB Output is correct
23 Correct 423 ms 254540 KB Output is correct
24 Correct 507 ms 254548 KB Output is correct
25 Correct 187 ms 254036 KB Output is correct
26 Correct 207 ms 254804 KB Output is correct
27 Correct 193 ms 254288 KB Output is correct
28 Correct 190 ms 254292 KB Output is correct
29 Correct 212 ms 254800 KB Output is correct
30 Correct 319 ms 254536 KB Output is correct
31 Correct 341 ms 254288 KB Output is correct
32 Correct 349 ms 254300 KB Output is correct
33 Correct 272 ms 254552 KB Output is correct
34 Correct 376 ms 254312 KB Output is correct
35 Correct 285 ms 254288 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20824 KB Output is correct
2 Correct 4074 ms 1867356 KB Output is correct
3 Correct 3449 ms 1873320 KB Output is correct
4 Correct 3300 ms 1874788 KB Output is correct
5 Correct 2920 ms 1874780 KB Output is correct
6 Correct 3945 ms 1873420 KB Output is correct
7 Correct 3790 ms 1871784 KB Output is correct
8 Correct 5 ms 20828 KB Output is correct
9 Correct 220 ms 254916 KB Output is correct
10 Correct 207 ms 255040 KB Output is correct
11 Correct 200 ms 254288 KB Output is correct
12 Correct 210 ms 254272 KB Output is correct
13 Correct 230 ms 254548 KB Output is correct
14 Correct 237 ms 254544 KB Output is correct
15 Correct 315 ms 254160 KB Output is correct
16 Correct 201 ms 254292 KB Output is correct
17 Correct 285 ms 254032 KB Output is correct
18 Correct 262 ms 254544 KB Output is correct
19 Correct 745 ms 254548 KB Output is correct
20 Correct 766 ms 254548 KB Output is correct
21 Correct 5 ms 20824 KB Output is correct
22 Correct 200 ms 254788 KB Output is correct
23 Correct 216 ms 254800 KB Output is correct
24 Correct 221 ms 254272 KB Output is correct
25 Correct 224 ms 254396 KB Output is correct
26 Correct 244 ms 254548 KB Output is correct
27 Correct 285 ms 254252 KB Output is correct
28 Correct 314 ms 254536 KB Output is correct
29 Correct 350 ms 254292 KB Output is correct
30 Correct 423 ms 254540 KB Output is correct
31 Correct 507 ms 254548 KB Output is correct
32 Correct 187 ms 254036 KB Output is correct
33 Correct 207 ms 254804 KB Output is correct
34 Correct 193 ms 254288 KB Output is correct
35 Correct 190 ms 254292 KB Output is correct
36 Correct 212 ms 254800 KB Output is correct
37 Correct 319 ms 254536 KB Output is correct
38 Correct 341 ms 254288 KB Output is correct
39 Correct 349 ms 254300 KB Output is correct
40 Correct 272 ms 254552 KB Output is correct
41 Correct 376 ms 254312 KB Output is correct
42 Correct 285 ms 254288 KB Output is correct
43 Correct 2 ms 16728 KB Output is correct
44 Correct 4 ms 20828 KB Output is correct
45 Correct 3549 ms 1877060 KB Output is correct
46 Correct 2887 ms 1873540 KB Output is correct
47 Correct 2821 ms 1874036 KB Output is correct
48 Correct 2744 ms 1876060 KB Output is correct
49 Correct 3235 ms 1877344 KB Output is correct
50 Correct 3762 ms 1876144 KB Output is correct
51 Correct 2819 ms 1872856 KB Output is correct
52 Correct 3805 ms 1871420 KB Output is correct
53 Correct 4486 ms 1871696 KB Output is correct
54 Correct 3809 ms 1876548 KB Output is correct
55 Correct 4184 ms 1875540 KB Output is correct
56 Correct 3633 ms 1876192 KB Output is correct
57 Correct 3568 ms 1876200 KB Output is correct
58 Correct 3631 ms 1876308 KB Output is correct
59 Correct 3878 ms 1876488 KB Output is correct
60 Correct 4757 ms 1875536 KB Output is correct
61 Correct 4577 ms 1875540 KB Output is correct