oj.uz

답안 #437023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437023 2021-06-25T16:06:48 Z model_code 던전 (IOI21_dungeons) C++17
100 / 100
 3202 ms 416532 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1312 KB Output is correct
3 Correct 5 ms 3532 KB Output is correct
4 Correct 104 ms 53672 KB Output is correct
5 Correct 5 ms 3404 KB Output is correct
6 Correct 117 ms 53896 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2124 KB Output is correct
2 Correct 784 ms 370964 KB Output is correct
3 Correct 734 ms 389820 KB Output is correct
4 Correct 623 ms 342288 KB Output is correct
5 Correct 1097 ms 337612 KB Output is correct
6 Correct 739 ms 366292 KB Output is correct
7 Correct 612 ms 368284 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2000 KB Output is correct
2 Correct 122 ms 43116 KB Output is correct
3 Correct 112 ms 42644 KB Output is correct
4 Correct 98 ms 53956 KB Output is correct
5 Correct 105 ms 53212 KB Output is correct
6 Correct 167 ms 42776 KB Output is correct
7 Correct 165 ms 42156 KB Output is correct
8 Correct 105 ms 53180 KB Output is correct
9 Correct 129 ms 53956 KB Output is correct
10 Correct 106 ms 54212 KB Output is correct
11 Correct 124 ms 55260 KB Output is correct
12 Correct 239 ms 41652 KB Output is correct
13 Correct 203 ms 41504 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2000 KB Output is correct
2 Correct 122 ms 43116 KB Output is correct
3 Correct 112 ms 42644 KB Output is correct
4 Correct 98 ms 53956 KB Output is correct
5 Correct 105 ms 53212 KB Output is correct
6 Correct 167 ms 42776 KB Output is correct
7 Correct 165 ms 42156 KB Output is correct
8 Correct 105 ms 53180 KB Output is correct
9 Correct 129 ms 53956 KB Output is correct
10 Correct 106 ms 54212 KB Output is correct
11 Correct 124 ms 55260 KB Output is correct
12 Correct 239 ms 41652 KB Output is correct
13 Correct 203 ms 41504 KB Output is correct
14 Correct 3 ms 1868 KB Output is correct
15 Correct 132 ms 42920 KB Output is correct
16 Correct 152 ms 44244 KB Output is correct
17 Correct 92 ms 43812 KB Output is correct
18 Correct 96 ms 43192 KB Output is correct
19 Correct 229 ms 43304 KB Output is correct
20 Correct 121 ms 44248 KB Output is correct
21 Correct 112 ms 43112 KB Output is correct
22 Correct 120 ms 55108 KB Output is correct
23 Correct 148 ms 55260 KB Output is correct
24 Correct 274 ms 44552 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2000 KB Output is correct
2 Correct 122 ms 43116 KB Output is correct
3 Correct 112 ms 42644 KB Output is correct
4 Correct 98 ms 53956 KB Output is correct
5 Correct 105 ms 53212 KB Output is correct
6 Correct 167 ms 42776 KB Output is correct
7 Correct 165 ms 42156 KB Output is correct
8 Correct 105 ms 53180 KB Output is correct
9 Correct 129 ms 53956 KB Output is correct
10 Correct 106 ms 54212 KB Output is correct
11 Correct 124 ms 55260 KB Output is correct
12 Correct 239 ms 41652 KB Output is correct
13 Correct 203 ms 41504 KB Output is correct
14 Correct 3 ms 1868 KB Output is correct
15 Correct 132 ms 42920 KB Output is correct
16 Correct 152 ms 44244 KB Output is correct
17 Correct 92 ms 43812 KB Output is correct
18 Correct 96 ms 43192 KB Output is correct
19 Correct 229 ms 43304 KB Output is correct
20 Correct 121 ms 44248 KB Output is correct
21 Correct 112 ms 43112 KB Output is correct
22 Correct 120 ms 55108 KB Output is correct
23 Correct 148 ms 55260 KB Output is correct
24 Correct 274 ms 44552 KB Output is correct
25 Correct 99 ms 48196 KB Output is correct
26 Correct 177 ms 49204 KB Output is correct
27 Correct 138 ms 55060 KB Output is correct
28 Correct 121 ms 50356 KB Output is correct
29 Correct 208 ms 49576 KB Output is correct
30 Correct 157 ms 51688 KB Output is correct
31 Correct 122 ms 50844 KB Output is correct
32 Correct 192 ms 55096 KB Output is correct
33 Correct 392 ms 48812 KB Output is correct
34 Correct 1119 ms 54440 KB Output is correct
35 Correct 258 ms 48452 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2124 KB Output is correct
2 Correct 784 ms 370964 KB Output is correct
3 Correct 734 ms 389820 KB Output is correct
4 Correct 623 ms 342288 KB Output is correct
5 Correct 1097 ms 337612 KB Output is correct
6 Correct 739 ms 366292 KB Output is correct
7 Correct 612 ms 368284 KB Output is correct
8 Correct 3 ms 2000 KB Output is correct
9 Correct 122 ms 43116 KB Output is correct
10 Correct 112 ms 42644 KB Output is correct
11 Correct 98 ms 53956 KB Output is correct
12 Correct 105 ms 53212 KB Output is correct
13 Correct 167 ms 42776 KB Output is correct
14 Correct 165 ms 42156 KB Output is correct
15 Correct 105 ms 53180 KB Output is correct
16 Correct 129 ms 53956 KB Output is correct
17 Correct 106 ms 54212 KB Output is correct
18 Correct 124 ms 55260 KB Output is correct
19 Correct 239 ms 41652 KB Output is correct
20 Correct 203 ms 41504 KB Output is correct
21 Correct 3 ms 1868 KB Output is correct
22 Correct 132 ms 42920 KB Output is correct
23 Correct 152 ms 44244 KB Output is correct
24 Correct 92 ms 43812 KB Output is correct
25 Correct 96 ms 43192 KB Output is correct
26 Correct 229 ms 43304 KB Output is correct
27 Correct 121 ms 44248 KB Output is correct
28 Correct 112 ms 43112 KB Output is correct
29 Correct 120 ms 55108 KB Output is correct
30 Correct 148 ms 55260 KB Output is correct
31 Correct 274 ms 44552 KB Output is correct
32 Correct 99 ms 48196 KB Output is correct
33 Correct 177 ms 49204 KB Output is correct
34 Correct 138 ms 55060 KB Output is correct
35 Correct 121 ms 50356 KB Output is correct
36 Correct 208 ms 49576 KB Output is correct
37 Correct 157 ms 51688 KB Output is correct
38 Correct 122 ms 50844 KB Output is correct
39 Correct 192 ms 55096 KB Output is correct
40 Correct 392 ms 48812 KB Output is correct
41 Correct 1119 ms 54440 KB Output is correct
42 Correct 258 ms 48452 KB Output is correct
43 Correct 1 ms 1356 KB Output is correct
44 Correct 3 ms 2124 KB Output is correct
45 Correct 1808 ms 377060 KB Output is correct
46 Correct 1561 ms 416532 KB Output is correct
47 Correct 1448 ms 383536 KB Output is correct
48 Correct 819 ms 317656 KB Output is correct
49 Correct 1837 ms 372160 KB Output is correct
50 Correct 761 ms 364740 KB Output is correct
51 Correct 697 ms 308204 KB Output is correct
52 Correct 732 ms 369660 KB Output is correct
53 Correct 2689 ms 416240 KB Output is correct
54 Correct 1351 ms 364704 KB Output is correct
55 Correct 2423 ms 411588 KB Output is correct
56 Correct 2217 ms 359052 KB Output is correct
57 Correct 2277 ms 348516 KB Output is correct
58 Correct 2457 ms 373384 KB Output is correct
59 Correct 3202 ms 415928 KB Output is correct
60 Correct 1920 ms 336224 KB Output is correct
61 Correct 1627 ms 336176 KB Output is correct