oj.uz

답안 #491293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
491293 2021-12-01T11:26:14 Z doowey 던전 (IOI21_dungeons) C++17
100 / 100
 3556 ms 1742292 KB 
#include <bits/stdc++.h>
#include "dungeons.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int LOG3 = 9;
const int BASE = 8;
const int LOG2 = 25;
const int N = (int)4e5;
const ll inf = (ll)1e18;

ll gain[LOG3][LOG2][N];
ll lim[LOG3][LOG2][N];
int go[LOG3][LOG2][N];
vector<int> S, P, W, L;
ll B[LOG3];
int n;

void init(int _n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	n = _n;
	B[0] = 1;
	for(int i = 1; i < LOG3; i ++ ){
        B[i] = B[i - 1] * BASE;
	}
	S = s;
	P = p;
	W = w;
	L = l;
	for(int C = 0; C < LOG3; C ++ ){
        for(int i = 0 ; i < n; i ++ ){
            if(S[i] < B[C]){
                if(w[i] == n){
                    go[C][0][i] = -1;
                }
                else{
                    go[C][0][i] = w[i];
                    gain[C][0][i] = S[i];
                    lim[C][0][i] = inf;
                }
            }
            else{
                if(l[i] == n){
                    go[C][0][i] = -1;
                }
                else{
                    go[C][0][i] = l[i];
                    gain[C][0][i] = p[i];
                    lim[C][0][i] = S[i];
                }
            }
        }
    }
    for(int C = 0 ; C < LOG3; C ++ ){
        for(int lg = 1; lg < LOG2; lg ++ ){
            for(int i = 0 ; i < n; i ++ ){
                if(go[C][lg-1][i] == -1 || go[C][lg-1][go[C][lg-1][i]] == -1){
                    go[C][lg][i] = -1;
                }
                else{
                    go[C][lg][i] = go[C][lg-1][go[C][lg-1][i]];
                    gain[C][lg][i] = gain[C][lg-1][i] + gain[C][lg-1][go[C][lg-1][i]];
                    lim[C][lg][i] = min(lim[C][lg-1][i], lim[C][lg-1][go[C][lg-1][i]] - gain[C][lg-1][i]);
                }
            }
        }
    }
	return;
}

ll simulate(int x, int Z) {
    ll strength = Z;
    int curb = 0;
    while(x != n){

        while(curb + 1 < LOG3 && B[curb + 1] <= strength){
            curb ++ ;
        }
        for(int lg = LOG2 - 1; lg >= 0 ; lg -- ){
            if(go[curb][lg][x] == -1) continue;
            if(strength >= lim[curb][lg][x]) continue;
            strength += gain[curb][lg][x];
            x = go[curb][lg][x];
        }

        if(strength >= S[x]){
            strength += S[x];
            x = W[x];
        }
        else{
            strength += P[x];
            x = L[x];
        }
        // one "special" manual move
    }
	return strength;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 2 ms 3916 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 117 ms 164552 KB Output is correct
5 Correct 6 ms 10188 KB Output is correct
6 Correct 114 ms 164396 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8908 KB Output is correct
2 Correct 1096 ms 1731736 KB Output is correct
3 Correct 1142 ms 1742292 KB Output is correct
4 Correct 1043 ms 1698276 KB Output is correct
5 Correct 1201 ms 1539076 KB Output is correct
6 Correct 1228 ms 1738192 KB Output is correct
7 Correct 1197 ms 1740476 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8908 KB Output is correct
2 Correct 282 ms 213040 KB Output is correct
3 Correct 247 ms 220472 KB Output is correct
4 Correct 140 ms 163540 KB Output is correct
5 Correct 171 ms 168184 KB Output is correct
6 Correct 321 ms 213164 KB Output is correct
7 Correct 278 ms 213512 KB Output is correct
8 Correct 172 ms 171928 KB Output is correct
9 Correct 126 ms 101128 KB Output is correct
10 Correct 171 ms 163504 KB Output is correct
11 Correct 180 ms 159364 KB Output is correct
12 Correct 332 ms 216840 KB Output is correct
13 Correct 220 ms 209636 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8908 KB Output is correct
2 Correct 282 ms 213040 KB Output is correct
3 Correct 247 ms 220472 KB Output is correct
4 Correct 140 ms 163540 KB Output is correct
5 Correct 171 ms 168184 KB Output is correct
6 Correct 321 ms 213164 KB Output is correct
7 Correct 278 ms 213512 KB Output is correct
8 Correct 172 ms 171928 KB Output is correct
9 Correct 126 ms 101128 KB Output is correct
10 Correct 171 ms 163504 KB Output is correct
11 Correct 180 ms 159364 KB Output is correct
12 Correct 332 ms 216840 KB Output is correct
13 Correct 220 ms 209636 KB Output is correct
14 Correct 5 ms 8908 KB Output is correct
15 Correct 186 ms 213728 KB Output is correct
16 Correct 240 ms 214000 KB Output is correct
17 Correct 167 ms 211420 KB Output is correct
18 Correct 185 ms 220444 KB Output is correct
19 Correct 276 ms 213552 KB Output is correct
20 Correct 229 ms 211916 KB Output is correct
21 Correct 259 ms 220728 KB Output is correct
22 Correct 178 ms 146300 KB Output is correct
23 Correct 196 ms 203984 KB Output is correct
24 Correct 320 ms 204084 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8908 KB Output is correct
2 Correct 282 ms 213040 KB Output is correct
3 Correct 247 ms 220472 KB Output is correct
4 Correct 140 ms 163540 KB Output is correct
5 Correct 171 ms 168184 KB Output is correct
6 Correct 321 ms 213164 KB Output is correct
7 Correct 278 ms 213512 KB Output is correct
8 Correct 172 ms 171928 KB Output is correct
9 Correct 126 ms 101128 KB Output is correct
10 Correct 171 ms 163504 KB Output is correct
11 Correct 180 ms 159364 KB Output is correct
12 Correct 332 ms 216840 KB Output is correct
13 Correct 220 ms 209636 KB Output is correct
14 Correct 5 ms 8908 KB Output is correct
15 Correct 186 ms 213728 KB Output is correct
16 Correct 240 ms 214000 KB Output is correct
17 Correct 167 ms 211420 KB Output is correct
18 Correct 185 ms 220444 KB Output is correct
19 Correct 276 ms 213552 KB Output is correct
20 Correct 229 ms 211916 KB Output is correct
21 Correct 259 ms 220728 KB Output is correct
22 Correct 178 ms 146300 KB Output is correct
23 Correct 196 ms 203984 KB Output is correct
24 Correct 320 ms 204084 KB Output is correct
25 Correct 154 ms 212804 KB Output is correct
26 Correct 241 ms 214196 KB Output is correct
27 Correct 203 ms 205900 KB Output is correct
28 Correct 189 ms 213496 KB Output is correct
29 Correct 269 ms 213920 KB Output is correct
30 Correct 265 ms 221380 KB Output is correct
31 Correct 263 ms 221140 KB Output is correct
32 Correct 380 ms 203872 KB Output is correct
33 Correct 959 ms 217264 KB Output is correct
34 Correct 1475 ms 217524 KB Output is correct
35 Correct 883 ms 209476 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8908 KB Output is correct
2 Correct 1096 ms 1731736 KB Output is correct
3 Correct 1142 ms 1742292 KB Output is correct
4 Correct 1043 ms 1698276 KB Output is correct
5 Correct 1201 ms 1539076 KB Output is correct
6 Correct 1228 ms 1738192 KB Output is correct
7 Correct 1197 ms 1740476 KB Output is correct
8 Correct 5 ms 8908 KB Output is correct
9 Correct 282 ms 213040 KB Output is correct
10 Correct 247 ms 220472 KB Output is correct
11 Correct 140 ms 163540 KB Output is correct
12 Correct 171 ms 168184 KB Output is correct
13 Correct 321 ms 213164 KB Output is correct
14 Correct 278 ms 213512 KB Output is correct
15 Correct 172 ms 171928 KB Output is correct
16 Correct 126 ms 101128 KB Output is correct
17 Correct 171 ms 163504 KB Output is correct
18 Correct 180 ms 159364 KB Output is correct
19 Correct 332 ms 216840 KB Output is correct
20 Correct 220 ms 209636 KB Output is correct
21 Correct 5 ms 8908 KB Output is correct
22 Correct 186 ms 213728 KB Output is correct
23 Correct 240 ms 214000 KB Output is correct
24 Correct 167 ms 211420 KB Output is correct
25 Correct 185 ms 220444 KB Output is correct
26 Correct 276 ms 213552 KB Output is correct
27 Correct 229 ms 211916 KB Output is correct
28 Correct 259 ms 220728 KB Output is correct
29 Correct 178 ms 146300 KB Output is correct
30 Correct 196 ms 203984 KB Output is correct
31 Correct 320 ms 204084 KB Output is correct
32 Correct 154 ms 212804 KB Output is correct
33 Correct 241 ms 214196 KB Output is correct
34 Correct 203 ms 205900 KB Output is correct
35 Correct 189 ms 213496 KB Output is correct
36 Correct 269 ms 213920 KB Output is correct
37 Correct 265 ms 221380 KB Output is correct
38 Correct 263 ms 221140 KB Output is correct
39 Correct 380 ms 203872 KB Output is correct
40 Correct 959 ms 217264 KB Output is correct
41 Correct 1475 ms 217524 KB Output is correct
42 Correct 883 ms 209476 KB Output is correct
43 Correct 2 ms 2764 KB Output is correct
44 Correct 5 ms 8908 KB Output is correct
45 Correct 1392 ms 1667400 KB Output is correct
46 Correct 1132 ms 1662880 KB Output is correct
47 Correct 1101 ms 1663228 KB Output is correct
48 Correct 1141 ms 1740952 KB Output is correct
49 Correct 1485 ms 1667808 KB Output is correct
50 Correct 1077 ms 1740684 KB Output is correct
51 Correct 1062 ms 1738776 KB Output is correct
52 Correct 1084 ms 1738536 KB Output is correct
53 Correct 2163 ms 1613608 KB Output is correct
54 Correct 2203 ms 1712532 KB Output is correct
55 Correct 2611 ms 1714496 KB Output is correct
56 Correct 2411 ms 1670772 KB Output is correct
57 Correct 3556 ms 1664768 KB Output is correct
58 Correct 2754 ms 1664836 KB Output is correct
59 Correct 2838 ms 1664968 KB Output is correct
60 Correct 2224 ms 1732104 KB Output is correct
61 Correct 2020 ms 1714076 KB Output is correct