oj.uz

Submission #624940

# Submission time Handle Problem Language Result Execution time Memory
624940 2022-08-09T07:35:22 Z leaked Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2916 ms 571748 KB 
#include <bits/stdc++.h>
#include "dungeons.h"

#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}

const int N=400'000+1;
const int lt=19;
const int c=6;

int up[N][c][lt];
int mn[N][c][lt];
int go[N][c][lt];

ll pode[N];
int ok=0;
int w[N],s[N],p[N],l[N];
int n;
vec<int> kek;


vec<int> ps;

void clever_init(){
    int pw=32;
    ps.pb(1);
    while(ps.back()<=(1e7)) ps.pb(ps.back()*pw);
    int lv=sz(ps);
    for(int i=n;i>=0;i--){
        pode[i]=pode[w[i]]+s[i];
    }
//    cout<<lv<<endl;
    for(int j=0;j+1<lv;j++){
        for(int i=0;i<=n;i++){
            if(s[i]>ps[j]&&s[i]<=(ps[j+1])){
                mn[i][j][0]=s[i];
                go[i][j][0]=l[i];
                up[i][j][0]=p[i];
            }
            else if(s[i]<=ps[j]){
                go[i][j][0]=w[i];
                up[i][j][0]=s[i];
                mn[i][j][0]=1e9;
            }
            else{
                go[i][j][0]=l[i];
                up[i][j][0]=p[i];
                mn[i][j][0]=1e9;
            }
        }
        for(int st=1;st<lt;st++){
            for(int i=0;i<=n;i++){
                mn[i][j][st]=min(mn[i][j][st-1],mn[go[i][j][st-1]][j][st-1]-up[i][j][st-1]);
                go[i][j][st]=go[go[i][j][st-1]][j][st-1];
                up[i][j][st]=min(ps.back(),up[i][j][st-1]+up[go[i][j][st-1]][j][st-1]);
            }
        }
    }
}

ll clever_query(int x,int z){
    ll sm=z;
    int t=upper_bound(all(ps),sm)-ps.begin()-1;
    while(sm<kek.back() && x!=n){
        while(sm>=(ps[t+1])) ++t;
        for(int j=lt-1;j>=0;j--){
            if(mn[x][t][j]>sm && (sm+up[x][t][j])<=kek.back() && (sm+up[x][t][j])<(ps[t+1])){
                sm+=up[x][t][j];
                x=go[x][t][j];
            }
        }
        if(sm<s[x]){
            sm+=p[x];
            x=l[x];
        }
        else{
            sm+=s[x];
            x=w[x];
        }
    }
    if(x!=n) assert(sm>=kek.back());
    sm+=pode[x];

    return sm;
}
void init(int n, vec<int> a,vec<int> b,vec<int> c,vec<int> d){
    for(int i=0;i<n;i++){
        s[i]=a[i];
        p[i]=b[i];
        w[i]=c[i];
        l[i]=d[i];
    }
    s[n]=0;w[n]=n;l[n]=n;p[n]=0;

    ::n=n;
    for(int i=0;i<n;i++) kek.pb(s[i]);
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());

    clever_init();
}

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


/*
3 2
13 13 13
4 3 1
2 2 3
1 0 1
0 1
2 3

*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 3 ms 3136 KB Output is correct
4 Correct 198 ms 71404 KB Output is correct
5 Correct 3 ms 3132 KB Output is correct
6 Correct 183 ms 71240 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 1609 ms 567012 KB Output is correct
3 Correct 1538 ms 567208 KB Output is correct
4 Correct 1511 ms 568544 KB Output is correct
5 Correct 1577 ms 568588 KB Output is correct
6 Correct 1757 ms 567016 KB Output is correct
7 Correct 1745 ms 565184 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1780 KB Output is correct
2 Correct 212 ms 72744 KB Output is correct
3 Correct 187 ms 73020 KB Output is correct
4 Correct 175 ms 72260 KB Output is correct
5 Correct 176 ms 72248 KB Output is correct
6 Correct 265 ms 72400 KB Output is correct
7 Correct 273 ms 72400 KB Output is correct
8 Correct 178 ms 72240 KB Output is correct
9 Correct 197 ms 72136 KB Output is correct
10 Correct 193 ms 72020 KB Output is correct
11 Correct 374 ms 72416 KB Output is correct
12 Correct 2578 ms 72396 KB Output is correct
13 Correct 2462 ms 72404 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1780 KB Output is correct
2 Correct 212 ms 72744 KB Output is correct
3 Correct 187 ms 73020 KB Output is correct
4 Correct 175 ms 72260 KB Output is correct
5 Correct 176 ms 72248 KB Output is correct
6 Correct 265 ms 72400 KB Output is correct
7 Correct 273 ms 72400 KB Output is correct
8 Correct 178 ms 72240 KB Output is correct
9 Correct 197 ms 72136 KB Output is correct
10 Correct 193 ms 72020 KB Output is correct
11 Correct 374 ms 72416 KB Output is correct
12 Correct 2578 ms 72396 KB Output is correct
13 Correct 2462 ms 72404 KB Output is correct
14 Correct 2 ms 1748 KB Output is correct
15 Correct 231 ms 72524 KB Output is correct
16 Correct 202 ms 72728 KB Output is correct
17 Correct 192 ms 72256 KB Output is correct
18 Correct 231 ms 72392 KB Output is correct
19 Correct 258 ms 72404 KB Output is correct
20 Correct 300 ms 72140 KB Output is correct
21 Correct 266 ms 72268 KB Output is correct
22 Correct 296 ms 72244 KB Output is correct
23 Correct 387 ms 72392 KB Output is correct
24 Correct 534 ms 72400 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1780 KB Output is correct
2 Correct 212 ms 72744 KB Output is correct
3 Correct 187 ms 73020 KB Output is correct
4 Correct 175 ms 72260 KB Output is correct
5 Correct 176 ms 72248 KB Output is correct
6 Correct 265 ms 72400 KB Output is correct
7 Correct 273 ms 72400 KB Output is correct
8 Correct 178 ms 72240 KB Output is correct
9 Correct 197 ms 72136 KB Output is correct
10 Correct 193 ms 72020 KB Output is correct
11 Correct 374 ms 72416 KB Output is correct
12 Correct 2578 ms 72396 KB Output is correct
13 Correct 2462 ms 72404 KB Output is correct
14 Correct 2 ms 1748 KB Output is correct
15 Correct 231 ms 72524 KB Output is correct
16 Correct 202 ms 72728 KB Output is correct
17 Correct 192 ms 72256 KB Output is correct
18 Correct 231 ms 72392 KB Output is correct
19 Correct 258 ms 72404 KB Output is correct
20 Correct 300 ms 72140 KB Output is correct
21 Correct 266 ms 72268 KB Output is correct
22 Correct 296 ms 72244 KB Output is correct
23 Correct 387 ms 72392 KB Output is correct
24 Correct 534 ms 72400 KB Output is correct
25 Correct 198 ms 71612 KB Output is correct
26 Correct 243 ms 72772 KB Output is correct
27 Correct 209 ms 72172 KB Output is correct
28 Correct 180 ms 72248 KB Output is correct
29 Correct 238 ms 72656 KB Output is correct
30 Correct 259 ms 72332 KB Output is correct
31 Correct 279 ms 72140 KB Output is correct
32 Correct 338 ms 72272 KB Output is correct
33 Correct 539 ms 72252 KB Output is correct
34 Correct 869 ms 72244 KB Output is correct
35 Correct 484 ms 72400 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 1609 ms 567012 KB Output is correct
3 Correct 1538 ms 567208 KB Output is correct
4 Correct 1511 ms 568544 KB Output is correct
5 Correct 1577 ms 568588 KB Output is correct
6 Correct 1757 ms 567016 KB Output is correct
7 Correct 1745 ms 565184 KB Output is correct
8 Correct 3 ms 1780 KB Output is correct
9 Correct 212 ms 72744 KB Output is correct
10 Correct 187 ms 73020 KB Output is correct
11 Correct 175 ms 72260 KB Output is correct
12 Correct 176 ms 72248 KB Output is correct
13 Correct 265 ms 72400 KB Output is correct
14 Correct 273 ms 72400 KB Output is correct
15 Correct 178 ms 72240 KB Output is correct
16 Correct 197 ms 72136 KB Output is correct
17 Correct 193 ms 72020 KB Output is correct
18 Correct 374 ms 72416 KB Output is correct
19 Correct 2578 ms 72396 KB Output is correct
20 Correct 2462 ms 72404 KB Output is correct
21 Correct 2 ms 1748 KB Output is correct
22 Correct 231 ms 72524 KB Output is correct
23 Correct 202 ms 72728 KB Output is correct
24 Correct 192 ms 72256 KB Output is correct
25 Correct 231 ms 72392 KB Output is correct
26 Correct 258 ms 72404 KB Output is correct
27 Correct 300 ms 72140 KB Output is correct
28 Correct 266 ms 72268 KB Output is correct
29 Correct 296 ms 72244 KB Output is correct
30 Correct 387 ms 72392 KB Output is correct
31 Correct 534 ms 72400 KB Output is correct
32 Correct 198 ms 71612 KB Output is correct
33 Correct 243 ms 72772 KB Output is correct
34 Correct 209 ms 72172 KB Output is correct
35 Correct 180 ms 72248 KB Output is correct
36 Correct 238 ms 72656 KB Output is correct
37 Correct 259 ms 72332 KB Output is correct
38 Correct 279 ms 72140 KB Output is correct
39 Correct 338 ms 72272 KB Output is correct
40 Correct 539 ms 72252 KB Output is correct
41 Correct 869 ms 72244 KB Output is correct
42 Correct 484 ms 72400 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 2 ms 1748 KB Output is correct
45 Correct 1951 ms 571720 KB Output is correct
46 Correct 1581 ms 567256 KB Output is correct
47 Correct 1536 ms 567460 KB Output is correct
48 Correct 1523 ms 569704 KB Output is correct
49 Correct 2053 ms 571748 KB Output is correct
50 Correct 1658 ms 569404 KB Output is correct
51 Correct 1557 ms 569628 KB Output is correct
52 Correct 1665 ms 567460 KB Output is correct
53 Correct 2404 ms 568124 KB Output is correct
54 Correct 2136 ms 569304 KB Output is correct
55 Correct 2676 ms 568300 KB Output is correct
56 Correct 2484 ms 569060 KB Output is correct
57 Correct 2654 ms 569112 KB Output is correct
58 Correct 2638 ms 568968 KB Output is correct
59 Correct 2729 ms 569196 KB Output is correct
60 Correct 2916 ms 568428 KB Output is correct
61 Correct 2823 ms 568356 KB Output is correct