oj.uz

답안 #720952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
720952 2023-04-09T21:23:13 Z urosk 던전 (IOI21_dungeons) C++17
100 / 100
 5266 ms 1785084 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define ll long long
#define llinf 1000000000000000000LL
#define pb push_back
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}

using namespace std;
#define maxn 400005
#define lg 25
#define lg2 9
#define B 8
ll n;
int a[maxn],b[maxn],w[maxn],l[maxn];
ll bs[lg2];
int st[lg2][lg][maxn];
ll sum[lg2][lg][maxn];
ll mx[lg2][lg][maxn];
void init(int N, vector<int> s, vector<int> p, vector<int> W, vector<int> L) {
    bs[0] = 1;
    for(int i = 1;i<lg2;i++) bs[i] = bs[i-1]*B;
    n = N;
    for(int i = 1;i<=n;i++) a[i] = s[i-1],b[i] = p[i-1],w[i] = W[i-1]+1,l[i] = L[i-1]+1;
    for(int j = 0;j<lg2;j++){
        for(int i = 1;i<=n;i++){
            if(bs[j]>a[i]){
                st[j][0][i] = w[i];
                sum[j][0][i] = a[i];
                mx[j][0][i] = llinf;
            }else{
                st[j][0][i] = l[i];
                sum[j][0][i] = b[i];
                mx[j][0][i] = a[i];
            }
        }
    }
    for(int j = 0;j<lg2;j++){
        for(int k = 1;k<lg;k++){
            for(int i = 1;i<=n;i++){
                st[j][k][i] = st[j][k-1][st[j][k-1][i]];
                sum[j][k][i] = sum[j][k-1][i] + sum[j][k-1][st[j][k-1][i]];
                mx[j][k][i] = min(mx[j][k-1][i],mx[j][k-1][st[j][k-1][i]]-sum[j][k-1][i]);
            }
        }
    }
    return;
}

long long simulate(int x, int Z) {
    ll z = Z;
    x++;
    int j = 0;
    while(x!=n+1){
        while(j+1<lg2&&bs[j+1]<=z) j++;
        for(int k = lg-1;k>=0;k--){
            if(st[j][k][x]==n+1) continue;
            if(z>=mx[j][k][x]) continue;
            z+=sum[j][k][x];
            x = st[j][k][x];
        }
        if(z>=a[x]){
            z+=a[x];
            x = w[x];
        }else{
            z+=b[x];
            x = l[x];
        }
    }
    return z;
}
/**
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3

3 2
9 9 9
3 1 2
2 2 3
1 0 1
0 1
2 3
**/

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5460 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 8 ms 14404 KB Output is correct
4 Correct 134 ms 228620 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 134 ms 228616 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 1040 ms 1785084 KB Output is correct
3 Correct 1006 ms 1781608 KB Output is correct
4 Correct 1041 ms 1781324 KB Output is correct
5 Correct 1213 ms 1781316 KB Output is correct
6 Correct 1177 ms 1781164 KB Output is correct
7 Correct 1173 ms 1781140 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 257 ms 228608 KB Output is correct
3 Correct 220 ms 228704 KB Output is correct
4 Correct 176 ms 229804 KB Output is correct
5 Correct 165 ms 229720 KB Output is correct
6 Correct 294 ms 229920 KB Output is correct
7 Correct 269 ms 230004 KB Output is correct
8 Correct 200 ms 229620 KB Output is correct
9 Correct 188 ms 229596 KB Output is correct
10 Correct 197 ms 229536 KB Output is correct
11 Correct 205 ms 229872 KB Output is correct
12 Correct 284 ms 230076 KB Output is correct
13 Correct 213 ms 229968 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 257 ms 228608 KB Output is correct
3 Correct 220 ms 228704 KB Output is correct
4 Correct 176 ms 229804 KB Output is correct
5 Correct 165 ms 229720 KB Output is correct
6 Correct 294 ms 229920 KB Output is correct
7 Correct 269 ms 230004 KB Output is correct
8 Correct 200 ms 229620 KB Output is correct
9 Correct 188 ms 229596 KB Output is correct
10 Correct 197 ms 229536 KB Output is correct
11 Correct 205 ms 229872 KB Output is correct
12 Correct 284 ms 230076 KB Output is correct
13 Correct 213 ms 229968 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 174 ms 230128 KB Output is correct
16 Correct 263 ms 230436 KB Output is correct
17 Correct 169 ms 229820 KB Output is correct
18 Correct 172 ms 229932 KB Output is correct
19 Correct 275 ms 230052 KB Output is correct
20 Correct 230 ms 229752 KB Output is correct
21 Correct 221 ms 229796 KB Output is correct
22 Correct 218 ms 229836 KB Output is correct
23 Correct 206 ms 229948 KB Output is correct
24 Correct 327 ms 230012 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 257 ms 228608 KB Output is correct
3 Correct 220 ms 228704 KB Output is correct
4 Correct 176 ms 229804 KB Output is correct
5 Correct 165 ms 229720 KB Output is correct
6 Correct 294 ms 229920 KB Output is correct
7 Correct 269 ms 230004 KB Output is correct
8 Correct 200 ms 229620 KB Output is correct
9 Correct 188 ms 229596 KB Output is correct
10 Correct 197 ms 229536 KB Output is correct
11 Correct 205 ms 229872 KB Output is correct
12 Correct 284 ms 230076 KB Output is correct
13 Correct 213 ms 229968 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 174 ms 230128 KB Output is correct
16 Correct 263 ms 230436 KB Output is correct
17 Correct 169 ms 229820 KB Output is correct
18 Correct 172 ms 229932 KB Output is correct
19 Correct 275 ms 230052 KB Output is correct
20 Correct 230 ms 229752 KB Output is correct
21 Correct 221 ms 229796 KB Output is correct
22 Correct 218 ms 229836 KB Output is correct
23 Correct 206 ms 229948 KB Output is correct
24 Correct 327 ms 230012 KB Output is correct
25 Correct 184 ms 229200 KB Output is correct
26 Correct 242 ms 230328 KB Output is correct
27 Correct 182 ms 229720 KB Output is correct
28 Correct 195 ms 229844 KB Output is correct
29 Correct 264 ms 230220 KB Output is correct
30 Correct 236 ms 229852 KB Output is correct
31 Correct 247 ms 229716 KB Output is correct
32 Correct 393 ms 229812 KB Output is correct
33 Correct 908 ms 229900 KB Output is correct
34 Correct 1401 ms 229704 KB Output is correct
35 Correct 809 ms 229832 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 1040 ms 1785084 KB Output is correct
3 Correct 1006 ms 1781608 KB Output is correct
4 Correct 1041 ms 1781324 KB Output is correct
5 Correct 1213 ms 1781316 KB Output is correct
6 Correct 1177 ms 1781164 KB Output is correct
7 Correct 1173 ms 1781140 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 257 ms 228608 KB Output is correct
10 Correct 220 ms 228704 KB Output is correct
11 Correct 176 ms 229804 KB Output is correct
12 Correct 165 ms 229720 KB Output is correct
13 Correct 294 ms 229920 KB Output is correct
14 Correct 269 ms 230004 KB Output is correct
15 Correct 200 ms 229620 KB Output is correct
16 Correct 188 ms 229596 KB Output is correct
17 Correct 197 ms 229536 KB Output is correct
18 Correct 205 ms 229872 KB Output is correct
19 Correct 284 ms 230076 KB Output is correct
20 Correct 213 ms 229968 KB Output is correct
21 Correct 6 ms 9940 KB Output is correct
22 Correct 174 ms 230128 KB Output is correct
23 Correct 263 ms 230436 KB Output is correct
24 Correct 169 ms 229820 KB Output is correct
25 Correct 172 ms 229932 KB Output is correct
26 Correct 275 ms 230052 KB Output is correct
27 Correct 230 ms 229752 KB Output is correct
28 Correct 221 ms 229796 KB Output is correct
29 Correct 218 ms 229836 KB Output is correct
30 Correct 206 ms 229948 KB Output is correct
31 Correct 327 ms 230012 KB Output is correct
32 Correct 184 ms 229200 KB Output is correct
33 Correct 242 ms 230328 KB Output is correct
34 Correct 182 ms 229720 KB Output is correct
35 Correct 195 ms 229844 KB Output is correct
36 Correct 264 ms 230220 KB Output is correct
37 Correct 236 ms 229852 KB Output is correct
38 Correct 247 ms 229716 KB Output is correct
39 Correct 393 ms 229812 KB Output is correct
40 Correct 908 ms 229900 KB Output is correct
41 Correct 1401 ms 229704 KB Output is correct
42 Correct 809 ms 229832 KB Output is correct
43 Correct 3 ms 5460 KB Output is correct
44 Correct 6 ms 9924 KB Output is correct
45 Correct 1482 ms 1785000 KB Output is correct
46 Correct 1126 ms 1784616 KB Output is correct
47 Correct 1109 ms 1784764 KB Output is correct
48 Correct 1209 ms 1784308 KB Output is correct
49 Correct 1681 ms 1784256 KB Output is correct
50 Correct 1211 ms 1783856 KB Output is correct
51 Correct 1178 ms 1783660 KB Output is correct
52 Correct 1240 ms 1783596 KB Output is correct
53 Correct 2712 ms 1783488 KB Output is correct
54 Correct 2548 ms 1783696 KB Output is correct
55 Correct 3055 ms 1783392 KB Output is correct
56 Correct 2612 ms 1783476 KB Output is correct
57 Correct 5266 ms 1783576 KB Output is correct
58 Correct 3035 ms 1783380 KB Output is correct
59 Correct 3048 ms 1783508 KB Output is correct
60 Correct 2281 ms 1781104 KB Output is correct
61 Correct 2131 ms 1781304 KB Output is correct