oj.uz

Submission #828975

# Submission time Handle Problem Language Result Execution time Memory
828975 2023-08-17T21:51:49 Z Liudas Dungeons Game (IOI21_dungeons) C++17
100 / 100
 1465 ms 424932 KB 
#include "dungeons.h"
#include <vector>
#include <assert.h>
#include <cstdio>
#define get_phase(x) min((63-__builtin_clzll(x)), maxphase-1)
#define win(node, phase) (get_phase(s[node]) < phase)
#define draw(node, phase) (get_phase(s[node]) == phase)
#define loc_out(x) (win(x, phase) ? w[x] : l[x])
#define sz_out(x) (win(x, phase) ? s[x] : p[x])

using namespace std;

const int maxphase = 25; // number of phases
const int maxpath = 25; // log2(maximum path length)
const int maxn = 4e5+5;
const long long inf = 1LL<<60;
int n;
vector<long long> s,p;
vector<int>w,l;

long long sze1[maxphase][maxn];
long long mx1[maxphase][maxn];
int loc1[maxphase][maxn];

long long sze2[maxpath][maxn];
long long mx2[maxpath][maxn];
int loc2[maxpath][maxn];

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
    n = _n; s = vector<long long>(begin(_s), end(_s)); p = vector<long long>(begin(_p), end(_p)); w = _w; l = _l;

    int dfs[n+1];
    int curr = 0;
    for(int phase=0; phase<maxphase; phase++) {
        // begin dfs to look for node with the correct phase
        for(int node=0; node<n; node++) {
            sze1[phase][node] = -1;
        }
        for(int node=0; node<n; node++) {
            if(sze1[phase][node] != -1) continue; // -1 for unvisited
            dfs[curr++] = node;
             do {
                sze1[phase][dfs[curr-1]] = -2;
                if(win(dfs[curr-1], phase)) {
                    dfs[curr] = w[dfs[curr-1]]; // win
                } else {
                    dfs[curr] = l[dfs[curr-1]]; // lose
                }
                curr++;
            } while(dfs[curr-1]!=n && sze1[phase][dfs[curr-1]] == -1 && !draw(dfs[curr-1], phase));

            if(dfs[curr-1]==n || draw(dfs[curr-1], phase)) {
                sze1[phase][dfs[curr-2]] = sz_out(dfs[curr-2]);
                mx1[phase][dfs[curr-2]] = win(dfs[curr-2], phase) ? inf : s[dfs[curr-2]];
                loc1[phase][dfs[curr-2]] = dfs[curr-1];
                for(int i=(int)curr-2; i>=1; i--) {
                    sze1[phase][dfs[i-1]] = min(sze1[phase][dfs[i]] + sz_out(dfs[i-1]), inf);
                    mx1[phase][dfs[i-1]] = min(win(dfs[i-1], phase) ? inf : s[dfs[i-1]],
                                               mx1[phase][dfs[i]] - sz_out(dfs[i-1]));
                    loc1[phase][dfs[i-1]] = loc1[phase][dfs[i]];
                }
            } else if(sze1[phase][dfs[curr-1]] >= 0) { // has a legit outgoing edge
                for(int i =(int) curr-1; i>=1; i--) {
                    sze1[phase][dfs[i-1]] = min(sze1[phase][dfs[i]] + sz_out(dfs[i-1]), inf);
                    mx1[phase][dfs[i-1]] = min(win(dfs[i-1], phase) ? inf : s[dfs[i-1]],
                                               mx1[phase][dfs[i]] - sz_out(dfs[i-1]));
                    loc1[phase][dfs[i-1]] = loc1[phase][dfs[i]];

                }
            }
            curr = 0;
        }
    }

    for(int node=0; node<n; node++) {
        sze2[0][node] = sze1[get_phase(s[node])][node];
        mx2[0][node] = mx1[get_phase(s[node])][node];
        loc2[0][node] = loc1[get_phase(s[node])][node];
    }

    sze2[0][n] = 0;
    mx2[0][n] = inf;
    loc2[0][n] = n;

    for(int len=1; len<maxpath; len++) {
        for(int node=0; node<=n; node++) {
            int l2 = loc2[len-1][node];
            if(l2!=-1) {
                sze2[len][node] = min(sze2[len-1][node] + sze2[len-1][l2],inf);
                mx2[len][node] = min(mx2[len-1][node],  mx2[len-1][l2]-sze2[len-1][node]);
                loc2[len][node] = loc2[len-1][l2];
            } else {
                sze2[len][node] = sze2[len-1][node];
                mx2[len][node] = mx2[len-1][node];
                loc2[len][node] = loc2[len-1][node];
            }
        }
    }
}

void step_forward(int &x, long long &z) {
    if(z >= s[x]) {
        z += s[x];
        x = w[x];
    } else {
        z += p[x];
        x = l[x];
    }
}

long long simulate(int x, int _z) {
    long long z = _z;
    int phase = get_phase(z);
    while(x<n) {
        assert(phase<maxphase);
        if(z < mx1[phase][x] && sze1[phase][x] != inf) {
            z += sze1[phase][x];
            x = loc1[phase][x];

            if(x==n) return z;
            for(int i=min(maxpath-1, 1+get_phase(s[x])); i>=0; i--) {
                if(z < mx2[i][x] && sze2[i][x] != inf) {
                    z += sze2[i][x];
                    x = loc2[i][x];
                }
            }
            if(x==n) return z;
            assert(z >= mx1[phase][x] || sze1[phase][x] == inf);
        }
        if (phase == get_phase(s[x])) {
            step_forward(x,z);
            phase = max(phase, get_phase(z));
        } else {
            phase++;
        }
    }
    return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 3 ms 3504 KB Output is correct
4 Correct 67 ms 52908 KB Output is correct
5 Correct 3 ms 3380 KB Output is correct
6 Correct 67 ms 53188 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2156 KB Output is correct
2 Correct 428 ms 374860 KB Output is correct
3 Correct 396 ms 394668 KB Output is correct
4 Correct 354 ms 349224 KB Output is correct
5 Correct 517 ms 344612 KB Output is correct
6 Correct 439 ms 371188 KB Output is correct
7 Correct 354 ms 371248 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2004 KB Output is correct
2 Correct 79 ms 41652 KB Output is correct
3 Correct 64 ms 41036 KB Output is correct
4 Correct 60 ms 52960 KB Output is correct
5 Correct 64 ms 52408 KB Output is correct
6 Correct 95 ms 41592 KB Output is correct
7 Correct 96 ms 41020 KB Output is correct
8 Correct 67 ms 52476 KB Output is correct
9 Correct 85 ms 53064 KB Output is correct
10 Correct 64 ms 53636 KB Output is correct
11 Correct 76 ms 54216 KB Output is correct
12 Correct 132 ms 40416 KB Output is correct
13 Correct 109 ms 40516 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2004 KB Output is correct
2 Correct 79 ms 41652 KB Output is correct
3 Correct 64 ms 41036 KB Output is correct
4 Correct 60 ms 52960 KB Output is correct
5 Correct 64 ms 52408 KB Output is correct
6 Correct 95 ms 41592 KB Output is correct
7 Correct 96 ms 41020 KB Output is correct
8 Correct 67 ms 52476 KB Output is correct
9 Correct 85 ms 53064 KB Output is correct
10 Correct 64 ms 53636 KB Output is correct
11 Correct 76 ms 54216 KB Output is correct
12 Correct 132 ms 40416 KB Output is correct
13 Correct 109 ms 40516 KB Output is correct
14 Correct 2 ms 1876 KB Output is correct
15 Correct 72 ms 41656 KB Output is correct
16 Correct 81 ms 42700 KB Output is correct
17 Correct 58 ms 42860 KB Output is correct
18 Correct 59 ms 42184 KB Output is correct
19 Correct 101 ms 42228 KB Output is correct
20 Correct 69 ms 43436 KB Output is correct
21 Correct 67 ms 42240 KB Output is correct
22 Correct 77 ms 54196 KB Output is correct
23 Correct 77 ms 54220 KB Output is correct
24 Correct 162 ms 44604 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2004 KB Output is correct
2 Correct 79 ms 41652 KB Output is correct
3 Correct 64 ms 41036 KB Output is correct
4 Correct 60 ms 52960 KB Output is correct
5 Correct 64 ms 52408 KB Output is correct
6 Correct 95 ms 41592 KB Output is correct
7 Correct 96 ms 41020 KB Output is correct
8 Correct 67 ms 52476 KB Output is correct
9 Correct 85 ms 53064 KB Output is correct
10 Correct 64 ms 53636 KB Output is correct
11 Correct 76 ms 54216 KB Output is correct
12 Correct 132 ms 40416 KB Output is correct
13 Correct 109 ms 40516 KB Output is correct
14 Correct 2 ms 1876 KB Output is correct
15 Correct 72 ms 41656 KB Output is correct
16 Correct 81 ms 42700 KB Output is correct
17 Correct 58 ms 42860 KB Output is correct
18 Correct 59 ms 42184 KB Output is correct
19 Correct 101 ms 42228 KB Output is correct
20 Correct 69 ms 43436 KB Output is correct
21 Correct 67 ms 42240 KB Output is correct
22 Correct 77 ms 54196 KB Output is correct
23 Correct 77 ms 54220 KB Output is correct
24 Correct 162 ms 44604 KB Output is correct
25 Correct 63 ms 48224 KB Output is correct
26 Correct 92 ms 49108 KB Output is correct
27 Correct 79 ms 55100 KB Output is correct
28 Correct 78 ms 50476 KB Output is correct
29 Correct 110 ms 49656 KB Output is correct
30 Correct 75 ms 51660 KB Output is correct
31 Correct 73 ms 50828 KB Output is correct
32 Correct 118 ms 55104 KB Output is correct
33 Correct 160 ms 48836 KB Output is correct
34 Correct 470 ms 54456 KB Output is correct
35 Correct 138 ms 48396 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2156 KB Output is correct
2 Correct 428 ms 374860 KB Output is correct
3 Correct 396 ms 394668 KB Output is correct
4 Correct 354 ms 349224 KB Output is correct
5 Correct 517 ms 344612 KB Output is correct
6 Correct 439 ms 371188 KB Output is correct
7 Correct 354 ms 371248 KB Output is correct
8 Correct 2 ms 2004 KB Output is correct
9 Correct 79 ms 41652 KB Output is correct
10 Correct 64 ms 41036 KB Output is correct
11 Correct 60 ms 52960 KB Output is correct
12 Correct 64 ms 52408 KB Output is correct
13 Correct 95 ms 41592 KB Output is correct
14 Correct 96 ms 41020 KB Output is correct
15 Correct 67 ms 52476 KB Output is correct
16 Correct 85 ms 53064 KB Output is correct
17 Correct 64 ms 53636 KB Output is correct
18 Correct 76 ms 54216 KB Output is correct
19 Correct 132 ms 40416 KB Output is correct
20 Correct 109 ms 40516 KB Output is correct
21 Correct 2 ms 1876 KB Output is correct
22 Correct 72 ms 41656 KB Output is correct
23 Correct 81 ms 42700 KB Output is correct
24 Correct 58 ms 42860 KB Output is correct
25 Correct 59 ms 42184 KB Output is correct
26 Correct 101 ms 42228 KB Output is correct
27 Correct 69 ms 43436 KB Output is correct
28 Correct 67 ms 42240 KB Output is correct
29 Correct 77 ms 54196 KB Output is correct
30 Correct 77 ms 54220 KB Output is correct
31 Correct 162 ms 44604 KB Output is correct
32 Correct 63 ms 48224 KB Output is correct
33 Correct 92 ms 49108 KB Output is correct
34 Correct 79 ms 55100 KB Output is correct
35 Correct 78 ms 50476 KB Output is correct
36 Correct 110 ms 49656 KB Output is correct
37 Correct 75 ms 51660 KB Output is correct
38 Correct 73 ms 50828 KB Output is correct
39 Correct 118 ms 55104 KB Output is correct
40 Correct 160 ms 48836 KB Output is correct
41 Correct 470 ms 54456 KB Output is correct
42 Correct 138 ms 48396 KB Output is correct
43 Correct 1 ms 1364 KB Output is correct
44 Correct 2 ms 2132 KB Output is correct
45 Correct 727 ms 388008 KB Output is correct
46 Correct 682 ms 422948 KB Output is correct
47 Correct 664 ms 390308 KB Output is correct
48 Correct 404 ms 326952 KB Output is correct
49 Correct 767 ms 383424 KB Output is correct
50 Correct 412 ms 373628 KB Output is correct
51 Correct 372 ms 317480 KB Output is correct
52 Correct 412 ms 376360 KB Output is correct
53 Correct 1067 ms 423932 KB Output is correct
54 Correct 640 ms 373544 KB Output is correct
55 Correct 1465 ms 419404 KB Output is correct
56 Correct 841 ms 367524 KB Output is correct
57 Correct 986 ms 357196 KB Output is correct
58 Correct 985 ms 382016 KB Output is correct
59 Correct 1272 ms 424932 KB Output is correct
60 Correct 758 ms 344504 KB Output is correct
61 Correct 720 ms 344428 KB Output is correct