oj.uz

Submission #442524

# Submission time Handle Problem Language Result Execution time Memory
442524 2021-07-08T05:54:16 Z JovanB Dungeons Game (IOI21_dungeons) C++17
100 / 100
 6439 ms 1786968 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 400000;
const int LOG2 = 24;
const int LOG8 = 8;

const ll INF = 1000000000000000000LL;

ll dp[LOG8+1][MAXN+5][LOG2+1];
ll dod[LOG8+1][MAXN+5][LOG2+1];
int gde[LOG8+1][MAXN+5][LOG2+1];

int s[MAXN+5];
int pl[MAXN+5];
int win[MAXN+5];
int lose[MAXN+5];
int step8[MAXN+5];

int N;

void init(int n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L){
    N = n;
    for(int i=0; i<n; i++){
        s[i] = S[i];
        pl[i] = P[i];
        win[i] = W[i];
        lose[i] = L[i];
    }
    s[n] = 0;
    pl[n] = 0;
    win[n] = n;
    lose[n] = n;
    step8[0] = 1;
    for(int i=1; i<=LOG8; i++) step8[i] = 8*step8[i-1];
    for(int k=0; k<=LOG8; k++){
        for(int i=0; i<=n; i++){
            if(step8[k] >= s[i]){
                dp[k][i][0] = INF;
                dod[k][i][0] = s[i];
                gde[k][i][0] = win[i];
            }
            else{
                dp[k][i][0] = s[i] - 1;
                dod[k][i][0] = pl[i];
                gde[k][i][0] = lose[i];
            }
        }
        for(int j=1; j<=LOG2; j++){
            for(int i=0; i<=n; i++){
                int h = gde[k][i][j-1];
                ll mndp = dp[k][i][j-1];
                ll udod = dod[k][i][j-1];
                for(int times=1; times<2; times++){
                    mndp = min(mndp, dp[k][h][j-1] - udod);
                    udod += dod[k][h][j-1];
                    h = gde[k][h][j-1];
                }
                gde[k][i][j] = h;
                dod[k][i][j] = udod;
                dp[k][i][j] = max(mndp, -5LL);
            }
        }
    }
	return;
}

ll simuliraj(int x, ll z){
    if(x == N) return z;
    int k = 0;
    for(int j=0; j<=LOG8; j++){
        if(step8[j] <= z) k = j;
    }
    if(k == LOG8) return z + dod[k][x][20];
    for(int j=LOG2; j>=0; j--){
        if(dp[k][x][j] >= z){
            z += dod[k][x][j];
            x = gde[k][x][j];
        }
    }
    if(x == N) return z;
    if(z >= s[x]) return simuliraj(win[x], z + s[x]);
    return simuliraj(lose[x], z + pl[x]);
}

long long simulate(int x, int z) {
    return simuliraj(x, z);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 8 ms 9420 KB Output is correct
4 Correct 498 ms 223008 KB Output is correct
5 Correct 9 ms 9420 KB Output is correct
6 Correct 493 ms 223040 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 4491 ms 1781184 KB Output is correct
3 Correct 4447 ms 1783080 KB Output is correct
4 Correct 4120 ms 1782884 KB Output is correct
5 Correct 3921 ms 1782836 KB Output is correct
6 Correct 4410 ms 1782572 KB Output is correct
7 Correct 4178 ms 1782464 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 567 ms 223944 KB Output is correct
3 Correct 511 ms 223944 KB Output is correct
4 Correct 543 ms 223948 KB Output is correct
5 Correct 520 ms 223980 KB Output is correct
6 Correct 584 ms 223984 KB Output is correct
7 Correct 546 ms 223924 KB Output is correct
8 Correct 539 ms 223920 KB Output is correct
9 Correct 514 ms 224016 KB Output is correct
10 Correct 527 ms 223952 KB Output is correct
11 Correct 631 ms 223960 KB Output is correct
12 Correct 820 ms 223940 KB Output is correct
13 Correct 651 ms 223984 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 567 ms 223944 KB Output is correct
3 Correct 511 ms 223944 KB Output is correct
4 Correct 543 ms 223948 KB Output is correct
5 Correct 520 ms 223980 KB Output is correct
6 Correct 584 ms 223984 KB Output is correct
7 Correct 546 ms 223924 KB Output is correct
8 Correct 539 ms 223920 KB Output is correct
9 Correct 514 ms 224016 KB Output is correct
10 Correct 527 ms 223952 KB Output is correct
11 Correct 631 ms 223960 KB Output is correct
12 Correct 820 ms 223940 KB Output is correct
13 Correct 651 ms 223984 KB Output is correct
14 Correct 5 ms 4940 KB Output is correct
15 Correct 539 ms 225244 KB Output is correct
16 Correct 573 ms 224692 KB Output is correct
17 Correct 558 ms 224284 KB Output is correct
18 Correct 580 ms 224920 KB Output is correct
19 Correct 585 ms 225048 KB Output is correct
20 Correct 587 ms 224844 KB Output is correct
21 Correct 604 ms 224896 KB Output is correct
22 Correct 582 ms 224888 KB Output is correct
23 Correct 665 ms 224932 KB Output is correct
24 Correct 817 ms 225064 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 567 ms 223944 KB Output is correct
3 Correct 511 ms 223944 KB Output is correct
4 Correct 543 ms 223948 KB Output is correct
5 Correct 520 ms 223980 KB Output is correct
6 Correct 584 ms 223984 KB Output is correct
7 Correct 546 ms 223924 KB Output is correct
8 Correct 539 ms 223920 KB Output is correct
9 Correct 514 ms 224016 KB Output is correct
10 Correct 527 ms 223952 KB Output is correct
11 Correct 631 ms 223960 KB Output is correct
12 Correct 820 ms 223940 KB Output is correct
13 Correct 651 ms 223984 KB Output is correct
14 Correct 5 ms 4940 KB Output is correct
15 Correct 539 ms 225244 KB Output is correct
16 Correct 573 ms 224692 KB Output is correct
17 Correct 558 ms 224284 KB Output is correct
18 Correct 580 ms 224920 KB Output is correct
19 Correct 585 ms 225048 KB Output is correct
20 Correct 587 ms 224844 KB Output is correct
21 Correct 604 ms 224896 KB Output is correct
22 Correct 582 ms 224888 KB Output is correct
23 Correct 665 ms 224932 KB Output is correct
24 Correct 817 ms 225064 KB Output is correct
25 Correct 502 ms 224424 KB Output is correct
26 Correct 556 ms 224956 KB Output is correct
27 Correct 521 ms 224612 KB Output is correct
28 Correct 527 ms 224688 KB Output is correct
29 Correct 583 ms 224776 KB Output is correct
30 Correct 642 ms 224640 KB Output is correct
31 Correct 623 ms 224768 KB Output is correct
32 Correct 808 ms 224696 KB Output is correct
33 Correct 1102 ms 224668 KB Output is correct
34 Correct 1489 ms 224816 KB Output is correct
35 Correct 813 ms 224848 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 4491 ms 1781184 KB Output is correct
3 Correct 4447 ms 1783080 KB Output is correct
4 Correct 4120 ms 1782884 KB Output is correct
5 Correct 3921 ms 1782836 KB Output is correct
6 Correct 4410 ms 1782572 KB Output is correct
7 Correct 4178 ms 1782464 KB Output is correct
8 Correct 5 ms 4940 KB Output is correct
9 Correct 567 ms 223944 KB Output is correct
10 Correct 511 ms 223944 KB Output is correct
11 Correct 543 ms 223948 KB Output is correct
12 Correct 520 ms 223980 KB Output is correct
13 Correct 584 ms 223984 KB Output is correct
14 Correct 546 ms 223924 KB Output is correct
15 Correct 539 ms 223920 KB Output is correct
16 Correct 514 ms 224016 KB Output is correct
17 Correct 527 ms 223952 KB Output is correct
18 Correct 631 ms 223960 KB Output is correct
19 Correct 820 ms 223940 KB Output is correct
20 Correct 651 ms 223984 KB Output is correct
21 Correct 5 ms 4940 KB Output is correct
22 Correct 539 ms 225244 KB Output is correct
23 Correct 573 ms 224692 KB Output is correct
24 Correct 558 ms 224284 KB Output is correct
25 Correct 580 ms 224920 KB Output is correct
26 Correct 585 ms 225048 KB Output is correct
27 Correct 587 ms 224844 KB Output is correct
28 Correct 604 ms 224896 KB Output is correct
29 Correct 582 ms 224888 KB Output is correct
30 Correct 665 ms 224932 KB Output is correct
31 Correct 817 ms 225064 KB Output is correct
32 Correct 502 ms 224424 KB Output is correct
33 Correct 556 ms 224956 KB Output is correct
34 Correct 521 ms 224612 KB Output is correct
35 Correct 527 ms 224688 KB Output is correct
36 Correct 583 ms 224776 KB Output is correct
37 Correct 642 ms 224640 KB Output is correct
38 Correct 623 ms 224768 KB Output is correct
39 Correct 808 ms 224696 KB Output is correct
40 Correct 1102 ms 224668 KB Output is correct
41 Correct 1489 ms 224816 KB Output is correct
42 Correct 813 ms 224848 KB Output is correct
43 Correct 1 ms 460 KB Output is correct
44 Correct 5 ms 4940 KB Output is correct
45 Correct 4972 ms 1782460 KB Output is correct
46 Correct 4111 ms 1781148 KB Output is correct
47 Correct 4057 ms 1781124 KB Output is correct
48 Correct 3873 ms 1781192 KB Output is correct
49 Correct 4977 ms 1781148 KB Output is correct
50 Correct 4397 ms 1781032 KB Output is correct
51 Correct 3898 ms 1781320 KB Output is correct
52 Correct 4361 ms 1781120 KB Output is correct
53 Correct 6389 ms 1781148 KB Output is correct
54 Correct 5247 ms 1781292 KB Output is correct
55 Correct 5776 ms 1781324 KB Output is correct
56 Correct 5675 ms 1781336 KB Output is correct
57 Correct 6267 ms 1781252 KB Output is correct
58 Correct 5956 ms 1781328 KB Output is correct
59 Correct 5923 ms 1781296 KB Output is correct
60 Correct 6439 ms 1781320 KB Output is correct
61 Correct 6082 ms 1786968 KB Output is correct