oj.uz

Submission #604527

# Submission time Handle Problem Language Result Execution time Memory
604527 2022-07-25T07:18:26 Z 2fat2code Dungeons Game (IOI21_dungeons) C++17
100 / 100
 6736 ms 2056848 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 400005;

// baza 10

int N, putere[9];
pair<pair<long long, long long>,int>lca[nmax][24][9];
vector<int>S, W;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    putere[0] = 1;
    for(int i=1;i<=8;i++) putere[i] = putere[i-1] * 8;
    for(auto &it : w) ++it;
    for(auto &it : l) ++it;
    S = s; W = w;
    N = n;
    for(int j=0;j<=8;j++){
        for(int i=1;i<=n;i++){
            if(s[i - 1] < putere[j]){
                lca[i][0][j].sc = w[i - 1];
                lca[i][0][j].fr.fr = s[i - 1];
                lca[i][0][j].fr.sc = -1e18;
            }
            else{
                lca[i][0][j].sc = l[i - 1];
                lca[i][0][j].fr.fr = p[i - 1];
                lca[i][0][j].fr.sc = -s[i - 1];
            }
        }
    }
    for(int k=1;k<=23;k++){
        for(int j=0;j<=8;j++){
            for(int i=1;i<=n;i++){
                lca[i][k][j].sc = lca[lca[i][k-1][j].sc][k-1][j].sc;
                lca[i][k][j].fr.fr = lca[i][k-1][j].fr.fr + lca[lca[i][k-1][j].sc][k-1][j].fr.fr;
                lca[i][k][j].fr.sc = max(lca[i][k-1][j].fr.sc, lca[i][k-1][j].fr.fr + lca[lca[i][k-1][j].sc][k-1][j].fr.sc);
            }
        }
    }
}

long long simulate(int x, int z) {
    int pos_curr = x + 1;
    long long putere_curr = z;
    int i = 0;
    int t = 0;
    while(pos_curr != N + 1){
        if(t == 7){
            i++;
            t = 0;
        }
        for(int j=23;j>=0;j--){
            if(lca[pos_curr][j][i].sc && lca[pos_curr][j][i].fr.sc + putere_curr < 0LL){
                putere_curr += lca[pos_curr][j][i].fr.fr;
                pos_curr = lca[pos_curr][j][i].sc;
            }
        }
        if(pos_curr == N + 1) break;
        else{
            ++t;
            putere_curr += (long long)S[pos_curr - 1];
            pos_curr = W[pos_curr - 1];
        }
    }
    return putere_curr;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 9 ms 10576 KB Output is correct
4 Correct 403 ms 256940 KB Output is correct
5 Correct 10 ms 10492 KB Output is correct
6 Correct 374 ms 256804 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 4038 ms 2047376 KB Output is correct
3 Correct 3923 ms 2047120 KB Output is correct
4 Correct 4157 ms 2046828 KB Output is correct
5 Correct 3377 ms 2046752 KB Output is correct
6 Correct 4003 ms 2045992 KB Output is correct
7 Correct 4065 ms 2045716 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 521 ms 256604 KB Output is correct
3 Correct 1353 ms 256676 KB Output is correct
4 Correct 596 ms 256716 KB Output is correct
5 Correct 675 ms 256676 KB Output is correct
6 Correct 487 ms 256668 KB Output is correct
7 Correct 459 ms 256684 KB Output is correct
8 Correct 657 ms 256680 KB Output is correct
9 Correct 512 ms 256680 KB Output is correct
10 Correct 565 ms 256748 KB Output is correct
11 Correct 605 ms 256676 KB Output is correct
12 Correct 1290 ms 256636 KB Output is correct
13 Correct 532 ms 256684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 521 ms 256604 KB Output is correct
3 Correct 1353 ms 256676 KB Output is correct
4 Correct 596 ms 256716 KB Output is correct
5 Correct 675 ms 256676 KB Output is correct
6 Correct 487 ms 256668 KB Output is correct
7 Correct 459 ms 256684 KB Output is correct
8 Correct 657 ms 256680 KB Output is correct
9 Correct 512 ms 256680 KB Output is correct
10 Correct 565 ms 256748 KB Output is correct
11 Correct 605 ms 256676 KB Output is correct
12 Correct 1290 ms 256636 KB Output is correct
13 Correct 532 ms 256684 KB Output is correct
14 Correct 5 ms 5460 KB Output is correct
15 Correct 589 ms 256904 KB Output is correct
16 Correct 526 ms 256904 KB Output is correct
17 Correct 918 ms 256916 KB Output is correct
18 Correct 1000 ms 256948 KB Output is correct
19 Correct 482 ms 256904 KB Output is correct
20 Correct 809 ms 256892 KB Output is correct
21 Correct 821 ms 256868 KB Output is correct
22 Correct 589 ms 256896 KB Output is correct
23 Correct 516 ms 256928 KB Output is correct
24 Correct 1237 ms 257004 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 521 ms 256604 KB Output is correct
3 Correct 1353 ms 256676 KB Output is correct
4 Correct 596 ms 256716 KB Output is correct
5 Correct 675 ms 256676 KB Output is correct
6 Correct 487 ms 256668 KB Output is correct
7 Correct 459 ms 256684 KB Output is correct
8 Correct 657 ms 256680 KB Output is correct
9 Correct 512 ms 256680 KB Output is correct
10 Correct 565 ms 256748 KB Output is correct
11 Correct 605 ms 256676 KB Output is correct
12 Correct 1290 ms 256636 KB Output is correct
13 Correct 532 ms 256684 KB Output is correct
14 Correct 5 ms 5460 KB Output is correct
15 Correct 589 ms 256904 KB Output is correct
16 Correct 526 ms 256904 KB Output is correct
17 Correct 918 ms 256916 KB Output is correct
18 Correct 1000 ms 256948 KB Output is correct
19 Correct 482 ms 256904 KB Output is correct
20 Correct 809 ms 256892 KB Output is correct
21 Correct 821 ms 256868 KB Output is correct
22 Correct 589 ms 256896 KB Output is correct
23 Correct 516 ms 256928 KB Output is correct
24 Correct 1237 ms 257004 KB Output is correct
25 Correct 395 ms 256120 KB Output is correct
26 Correct 526 ms 256672 KB Output is correct
27 Correct 560 ms 256680 KB Output is correct
28 Correct 520 ms 256800 KB Output is correct
29 Correct 543 ms 256684 KB Output is correct
30 Correct 830 ms 256728 KB Output is correct
31 Correct 809 ms 256868 KB Output is correct
32 Correct 1235 ms 257052 KB Output is correct
33 Correct 1804 ms 257044 KB Output is correct
34 Correct 2210 ms 257600 KB Output is correct
35 Correct 1117 ms 257832 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 4038 ms 2047376 KB Output is correct
3 Correct 3923 ms 2047120 KB Output is correct
4 Correct 4157 ms 2046828 KB Output is correct
5 Correct 3377 ms 2046752 KB Output is correct
6 Correct 4003 ms 2045992 KB Output is correct
7 Correct 4065 ms 2045716 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 521 ms 256604 KB Output is correct
10 Correct 1353 ms 256676 KB Output is correct
11 Correct 596 ms 256716 KB Output is correct
12 Correct 675 ms 256676 KB Output is correct
13 Correct 487 ms 256668 KB Output is correct
14 Correct 459 ms 256684 KB Output is correct
15 Correct 657 ms 256680 KB Output is correct
16 Correct 512 ms 256680 KB Output is correct
17 Correct 565 ms 256748 KB Output is correct
18 Correct 605 ms 256676 KB Output is correct
19 Correct 1290 ms 256636 KB Output is correct
20 Correct 532 ms 256684 KB Output is correct
21 Correct 5 ms 5460 KB Output is correct
22 Correct 589 ms 256904 KB Output is correct
23 Correct 526 ms 256904 KB Output is correct
24 Correct 918 ms 256916 KB Output is correct
25 Correct 1000 ms 256948 KB Output is correct
26 Correct 482 ms 256904 KB Output is correct
27 Correct 809 ms 256892 KB Output is correct
28 Correct 821 ms 256868 KB Output is correct
29 Correct 589 ms 256896 KB Output is correct
30 Correct 516 ms 256928 KB Output is correct
31 Correct 1237 ms 257004 KB Output is correct
32 Correct 395 ms 256120 KB Output is correct
33 Correct 526 ms 256672 KB Output is correct
34 Correct 560 ms 256680 KB Output is correct
35 Correct 520 ms 256800 KB Output is correct
36 Correct 543 ms 256684 KB Output is correct
37 Correct 830 ms 256728 KB Output is correct
38 Correct 809 ms 256868 KB Output is correct
39 Correct 1235 ms 257052 KB Output is correct
40 Correct 1804 ms 257044 KB Output is correct
41 Correct 2210 ms 257600 KB Output is correct
42 Correct 1117 ms 257832 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 5 ms 5460 KB Output is correct
45 Correct 3947 ms 2056752 KB Output is correct
46 Correct 3659 ms 2052740 KB Output is correct
47 Correct 3907 ms 2053124 KB Output is correct
48 Correct 4272 ms 2055292 KB Output is correct
49 Correct 3962 ms 2056848 KB Output is correct
50 Correct 3814 ms 2055004 KB Output is correct
51 Correct 3445 ms 2055328 KB Output is correct
52 Correct 3767 ms 2052996 KB Output is correct
53 Correct 6118 ms 2053880 KB Output is correct
54 Correct 5165 ms 2054880 KB Output is correct
55 Correct 5904 ms 2053920 KB Output is correct
56 Correct 5291 ms 2054568 KB Output is correct
57 Correct 5875 ms 2054676 KB Output is correct
58 Correct 5789 ms 2054684 KB Output is correct
59 Correct 5638 ms 2054812 KB Output is correct
60 Correct 6586 ms 2054028 KB Output is correct
61 Correct 6736 ms 2053944 KB Output is correct