oj.uz

Submission #990942

# Submission time Handle Problem Language Result Execution time Memory
990942 2024-05-31T20:44:20 Z AdamGS Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1872732 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) {
        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(nxt[x][i][j]<n && ile[x][i][j]>z) {
      z+=sum[x][i][j];
      x=nxt[x][i][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 25164 KB Output is correct
4 Correct 197 ms 253220 KB Output is correct
5 Correct 8 ms 25180 KB Output is correct
6 Correct 196 ms 253244 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 4196 ms 1871452 KB Output is correct
3 Correct 3733 ms 1871440 KB Output is correct
4 Correct 3806 ms 1871952 KB Output is correct
5 Correct 3327 ms 1871708 KB Output is correct
6 Correct 4828 ms 1870940 KB Output is correct
7 Correct 4353 ms 1870420 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20824 KB Output is correct
2 Correct 233 ms 254548 KB Output is correct
3 Correct 219 ms 254544 KB Output is correct
4 Correct 224 ms 254284 KB Output is correct
5 Correct 223 ms 254292 KB Output is correct
6 Correct 262 ms 254288 KB Output is correct
7 Correct 271 ms 254292 KB Output is correct
8 Correct 392 ms 254548 KB Output is correct
9 Correct 210 ms 254036 KB Output is correct
10 Correct 365 ms 254032 KB Output is correct
11 Correct 330 ms 254292 KB Output is correct
12 Correct 1164 ms 254288 KB Output is correct
13 Correct 1191 ms 254288 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20824 KB Output is correct
2 Correct 233 ms 254548 KB Output is correct
3 Correct 219 ms 254544 KB Output is correct
4 Correct 224 ms 254284 KB Output is correct
5 Correct 223 ms 254292 KB Output is correct
6 Correct 262 ms 254288 KB Output is correct
7 Correct 271 ms 254292 KB Output is correct
8 Correct 392 ms 254548 KB Output is correct
9 Correct 210 ms 254036 KB Output is correct
10 Correct 365 ms 254032 KB Output is correct
11 Correct 330 ms 254292 KB Output is correct
12 Correct 1164 ms 254288 KB Output is correct
13 Correct 1191 ms 254288 KB Output is correct
14 Correct 5 ms 20828 KB Output is correct
15 Correct 209 ms 254356 KB Output is correct
16 Correct 244 ms 254540 KB Output is correct
17 Correct 255 ms 254036 KB Output is correct
18 Correct 249 ms 254288 KB Output is correct
19 Correct 257 ms 254132 KB Output is correct
20 Correct 342 ms 254036 KB Output is correct
21 Correct 398 ms 254032 KB Output is correct
22 Correct 408 ms 254292 KB Output is correct
23 Correct 571 ms 254288 KB Output is correct
24 Correct 745 ms 254288 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20824 KB Output is correct
2 Correct 233 ms 254548 KB Output is correct
3 Correct 219 ms 254544 KB Output is correct
4 Correct 224 ms 254284 KB Output is correct
5 Correct 223 ms 254292 KB Output is correct
6 Correct 262 ms 254288 KB Output is correct
7 Correct 271 ms 254292 KB Output is correct
8 Correct 392 ms 254548 KB Output is correct
9 Correct 210 ms 254036 KB Output is correct
10 Correct 365 ms 254032 KB Output is correct
11 Correct 330 ms 254292 KB Output is correct
12 Correct 1164 ms 254288 KB Output is correct
13 Correct 1191 ms 254288 KB Output is correct
14 Correct 5 ms 20828 KB Output is correct
15 Correct 209 ms 254356 KB Output is correct
16 Correct 244 ms 254540 KB Output is correct
17 Correct 255 ms 254036 KB Output is correct
18 Correct 249 ms 254288 KB Output is correct
19 Correct 257 ms 254132 KB Output is correct
20 Correct 342 ms 254036 KB Output is correct
21 Correct 398 ms 254032 KB Output is correct
22 Correct 408 ms 254292 KB Output is correct
23 Correct 571 ms 254288 KB Output is correct
24 Correct 745 ms 254288 KB Output is correct
25 Correct 214 ms 253404 KB Output is correct
26 Correct 236 ms 254548 KB Output is correct
27 Correct 211 ms 254036 KB Output is correct
28 Correct 210 ms 254224 KB Output is correct
29 Correct 230 ms 254544 KB Output is correct
30 Correct 410 ms 254284 KB Output is correct
31 Correct 475 ms 254036 KB Output is correct
32 Correct 457 ms 254284 KB Output is correct
33 Correct 280 ms 254288 KB Output is correct
34 Correct 362 ms 254288 KB Output is correct
35 Correct 347 ms 254288 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 4196 ms 1871452 KB Output is correct
3 Correct 3733 ms 1871440 KB Output is correct
4 Correct 3806 ms 1871952 KB Output is correct
5 Correct 3327 ms 1871708 KB Output is correct
6 Correct 4828 ms 1870940 KB Output is correct
7 Correct 4353 ms 1870420 KB Output is correct
8 Correct 5 ms 20824 KB Output is correct
9 Correct 233 ms 254548 KB Output is correct
10 Correct 219 ms 254544 KB Output is correct
11 Correct 224 ms 254284 KB Output is correct
12 Correct 223 ms 254292 KB Output is correct
13 Correct 262 ms 254288 KB Output is correct
14 Correct 271 ms 254292 KB Output is correct
15 Correct 392 ms 254548 KB Output is correct
16 Correct 210 ms 254036 KB Output is correct
17 Correct 365 ms 254032 KB Output is correct
18 Correct 330 ms 254292 KB Output is correct
19 Correct 1164 ms 254288 KB Output is correct
20 Correct 1191 ms 254288 KB Output is correct
21 Correct 5 ms 20828 KB Output is correct
22 Correct 209 ms 254356 KB Output is correct
23 Correct 244 ms 254540 KB Output is correct
24 Correct 255 ms 254036 KB Output is correct
25 Correct 249 ms 254288 KB Output is correct
26 Correct 257 ms 254132 KB Output is correct
27 Correct 342 ms 254036 KB Output is correct
28 Correct 398 ms 254032 KB Output is correct
29 Correct 408 ms 254292 KB Output is correct
30 Correct 571 ms 254288 KB Output is correct
31 Correct 745 ms 254288 KB Output is correct
32 Correct 214 ms 253404 KB Output is correct
33 Correct 236 ms 254548 KB Output is correct
34 Correct 211 ms 254036 KB Output is correct
35 Correct 210 ms 254224 KB Output is correct
36 Correct 230 ms 254544 KB Output is correct
37 Correct 410 ms 254284 KB Output is correct
38 Correct 475 ms 254036 KB Output is correct
39 Correct 457 ms 254284 KB Output is correct
40 Correct 280 ms 254288 KB Output is correct
41 Correct 362 ms 254288 KB Output is correct
42 Correct 347 ms 254288 KB Output is correct
43 Correct 2 ms 16732 KB Output is correct
44 Correct 4 ms 20828 KB Output is correct
45 Correct 4145 ms 1872732 KB Output is correct
46 Correct 3486 ms 1870548 KB Output is correct
47 Correct 3542 ms 1869904 KB Output is correct
48 Correct 3285 ms 1870676 KB Output is correct
49 Correct 4223 ms 1871448 KB Output is correct
50 Correct 4192 ms 1869904 KB Output is correct
51 Correct 3068 ms 1867336 KB Output is correct
52 Correct 4586 ms 1867268 KB Output is correct
53 Execution timed out 7099 ms 1719632 KB Time limit exceeded
54 Halted 0 ms 0 KB -