oj.uz

답안 #442807

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442807 2021-07-09T07:37:51 Z SorahISA 던전 (IOI21_dungeons) C++17
100 / 100
 5589 ms 1125688 KB 
#include "dungeons.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

namespace {

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 4E5 + 5;
// const int maxn = 5E4 + 5;
const int lgmx = 24 + 1;
const int INF = INT_MAX;

int N;
vector<int> S, P, W, L;

vector<int> dep(maxn);

int sum[lgmx/4+1][lgmx][maxn];
int32_t anc[lgmx/4+1][lgmx][maxn], mnm[lgmx/4+1][lgmx][maxn];

} /// end of namespace

void init(int32_t _N, vector<int32_t> _S, vector<int32_t> _P, vector<int32_t> _W, vector<int32_t> _L) {
    N = _N;
    for (auto &x : _S) S.eb(x);
    for (auto &x : _P) P.eb(x);
    for (auto &x : _W) W.eb(x);
    for (auto &x : _L) L.eb(x);
    S.eb(0), P.eb(0), W.eb(N), L.eb(N);
    
    memset(anc, 0x00, sizeof(anc));
    memset(sum, 0x00, sizeof(sum));
    memset(mnm, 0x00, sizeof(mnm));
    
    for (int i = N-1; i >= 0; --i) dep[i] = dep[W[i]] + S[i];
    
    for (int lvl = 0; lvl <= lgmx/4; ++lvl) {
        
        /**
         * Assume strength is in [2^{4*lvl-4}, 2^{4*lvl}), every opponent with strength
         * greater or equal to 2^{4*lvl} is ignored and you lose immediately as we
         * only consider opponents with strength less than 2^{4*lvl} in this level.
        **/
        
        for (int i = 0; i <= N; ++i) {
            anc[lvl][0][i] = S[i] < (1<<(4*lvl)) ? W[i] : L[i];
            sum[lvl][0][i] = S[i] < (1<<(4*lvl)) ? S[i] : P[i];
            mnm[lvl][0][i] = S[i] < (1<<(4*lvl)) ? INF  : S[i];
        }
        
        for (int lay = 1; lay < lgmx; ++lay) {
            for (int i = 0; i <= N; ++i) {
                int32_t par = anc[lvl][lay-1][i];
                anc[lvl][lay][i] = anc[lvl][lay-1][par];
                sum[lvl][lay][i] = sum[lvl][lay-1][i] + sum[lvl][lay-1][par];
                int32_t tmp = mnm[lvl][lay-1][par];
                if (tmp != INF) tmp -= sum[lvl][lay-1][i];
                mnm[lvl][lay][i] = min(mnm[lvl][lay-1][i], max(0, tmp));
            }
        }
        
    }
}

int simulate(int32_t now, int32_t _Z) {
    int Z = _Z;
    for (int lvl = 0; lvl <= lgmx/4; ++lvl) {
        // int lvl = __lg(Z) / 4;
        for (int _ = 0; _ < 1<<4; ++_) {
            for (int lay = lgmx-1; lay >= 0; --lay) {
                if (Z < mnm[lvl][lay][now]) {
                    Z += sum[lvl][lay][now];
                    now = anc[lvl][lay][now]; 
                }
            }
            // cerr << "lvl = " << lvl << ", Z = " << Z << ", now = " << now << "\n";
            if (Z >= S[now]) Z += S[now], now = W[now];
            else             Z += P[now], now = L[now];
            // cerr << "lvl = " << lvl << ", Z = " << Z << ", now = " << now << "\n";
        }
    }
    return Z + dep[now];
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 483 ms 1099236 KB Output is correct
2 Correct 526 ms 1099228 KB Output is correct
3 Correct 483 ms 1099412 KB Output is correct
4 Correct 604 ms 1102680 KB Output is correct
5 Correct 490 ms 1099420 KB Output is correct
6 Correct 585 ms 1102712 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 504 ms 1099352 KB Output is correct
2 Correct 2213 ms 1125536 KB Output is correct
3 Correct 2146 ms 1125468 KB Output is correct
4 Correct 2311 ms 1125436 KB Output is correct
5 Correct 2528 ms 1125428 KB Output is correct
6 Correct 2135 ms 1125608 KB Output is correct
7 Correct 3103 ms 1125448 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 510 ms 1099424 KB Output is correct
2 Correct 1644 ms 1103304 KB Output is correct
3 Correct 1114 ms 1103332 KB Output is correct
4 Correct 1509 ms 1103436 KB Output is correct
5 Correct 1576 ms 1103584 KB Output is correct
6 Correct 1759 ms 1103380 KB Output is correct
7 Correct 1742 ms 1103408 KB Output is correct
8 Correct 1518 ms 1103488 KB Output is correct
9 Correct 1628 ms 1103420 KB Output is correct
10 Correct 1747 ms 1103496 KB Output is correct
11 Correct 1621 ms 1103500 KB Output is correct
12 Correct 1065 ms 1103492 KB Output is correct
13 Correct 1688 ms 1103420 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 510 ms 1099424 KB Output is correct
2 Correct 1644 ms 1103304 KB Output is correct
3 Correct 1114 ms 1103332 KB Output is correct
4 Correct 1509 ms 1103436 KB Output is correct
5 Correct 1576 ms 1103584 KB Output is correct
6 Correct 1759 ms 1103380 KB Output is correct
7 Correct 1742 ms 1103408 KB Output is correct
8 Correct 1518 ms 1103488 KB Output is correct
9 Correct 1628 ms 1103420 KB Output is correct
10 Correct 1747 ms 1103496 KB Output is correct
11 Correct 1621 ms 1103500 KB Output is correct
12 Correct 1065 ms 1103492 KB Output is correct
13 Correct 1688 ms 1103420 KB Output is correct
14 Correct 518 ms 1099436 KB Output is correct
15 Correct 1467 ms 1103524 KB Output is correct
16 Correct 1601 ms 1103548 KB Output is correct
17 Correct 1465 ms 1103560 KB Output is correct
18 Correct 1480 ms 1103400 KB Output is correct
19 Correct 1648 ms 1103388 KB Output is correct
20 Correct 1471 ms 1103472 KB Output is correct
21 Correct 1424 ms 1103512 KB Output is correct
22 Correct 1527 ms 1103444 KB Output is correct
23 Correct 1513 ms 1103572 KB Output is correct
24 Correct 1704 ms 1103556 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 510 ms 1099424 KB Output is correct
2 Correct 1644 ms 1103304 KB Output is correct
3 Correct 1114 ms 1103332 KB Output is correct
4 Correct 1509 ms 1103436 KB Output is correct
5 Correct 1576 ms 1103584 KB Output is correct
6 Correct 1759 ms 1103380 KB Output is correct
7 Correct 1742 ms 1103408 KB Output is correct
8 Correct 1518 ms 1103488 KB Output is correct
9 Correct 1628 ms 1103420 KB Output is correct
10 Correct 1747 ms 1103496 KB Output is correct
11 Correct 1621 ms 1103500 KB Output is correct
12 Correct 1065 ms 1103492 KB Output is correct
13 Correct 1688 ms 1103420 KB Output is correct
14 Correct 518 ms 1099436 KB Output is correct
15 Correct 1467 ms 1103524 KB Output is correct
16 Correct 1601 ms 1103548 KB Output is correct
17 Correct 1465 ms 1103560 KB Output is correct
18 Correct 1480 ms 1103400 KB Output is correct
19 Correct 1648 ms 1103388 KB Output is correct
20 Correct 1471 ms 1103472 KB Output is correct
21 Correct 1424 ms 1103512 KB Output is correct
22 Correct 1527 ms 1103444 KB Output is correct
23 Correct 1513 ms 1103572 KB Output is correct
24 Correct 1704 ms 1103556 KB Output is correct
25 Correct 617 ms 1102788 KB Output is correct
26 Correct 1597 ms 1103488 KB Output is correct
27 Correct 1547 ms 1103436 KB Output is correct
28 Correct 1568 ms 1103408 KB Output is correct
29 Correct 1635 ms 1103604 KB Output is correct
30 Correct 1380 ms 1103364 KB Output is correct
31 Correct 1314 ms 1103424 KB Output is correct
32 Correct 1609 ms 1103420 KB Output is correct
33 Correct 1897 ms 1103488 KB Output is correct
34 Correct 2930 ms 1103432 KB Output is correct
35 Correct 2788 ms 1103436 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 504 ms 1099352 KB Output is correct
2 Correct 2213 ms 1125536 KB Output is correct
3 Correct 2146 ms 1125468 KB Output is correct
4 Correct 2311 ms 1125436 KB Output is correct
5 Correct 2528 ms 1125428 KB Output is correct
6 Correct 2135 ms 1125608 KB Output is correct
7 Correct 3103 ms 1125448 KB Output is correct
8 Correct 510 ms 1099424 KB Output is correct
9 Correct 1644 ms 1103304 KB Output is correct
10 Correct 1114 ms 1103332 KB Output is correct
11 Correct 1509 ms 1103436 KB Output is correct
12 Correct 1576 ms 1103584 KB Output is correct
13 Correct 1759 ms 1103380 KB Output is correct
14 Correct 1742 ms 1103408 KB Output is correct
15 Correct 1518 ms 1103488 KB Output is correct
16 Correct 1628 ms 1103420 KB Output is correct
17 Correct 1747 ms 1103496 KB Output is correct
18 Correct 1621 ms 1103500 KB Output is correct
19 Correct 1065 ms 1103492 KB Output is correct
20 Correct 1688 ms 1103420 KB Output is correct
21 Correct 518 ms 1099436 KB Output is correct
22 Correct 1467 ms 1103524 KB Output is correct
23 Correct 1601 ms 1103548 KB Output is correct
24 Correct 1465 ms 1103560 KB Output is correct
25 Correct 1480 ms 1103400 KB Output is correct
26 Correct 1648 ms 1103388 KB Output is correct
27 Correct 1471 ms 1103472 KB Output is correct
28 Correct 1424 ms 1103512 KB Output is correct
29 Correct 1527 ms 1103444 KB Output is correct
30 Correct 1513 ms 1103572 KB Output is correct
31 Correct 1704 ms 1103556 KB Output is correct
32 Correct 617 ms 1102788 KB Output is correct
33 Correct 1597 ms 1103488 KB Output is correct
34 Correct 1547 ms 1103436 KB Output is correct
35 Correct 1568 ms 1103408 KB Output is correct
36 Correct 1635 ms 1103604 KB Output is correct
37 Correct 1380 ms 1103364 KB Output is correct
38 Correct 1314 ms 1103424 KB Output is correct
39 Correct 1609 ms 1103420 KB Output is correct
40 Correct 1897 ms 1103488 KB Output is correct
41 Correct 2930 ms 1103432 KB Output is correct
42 Correct 2788 ms 1103436 KB Output is correct
43 Correct 480 ms 1099240 KB Output is correct
44 Correct 508 ms 1099328 KB Output is correct
45 Correct 2864 ms 1125688 KB Output is correct
46 Correct 2517 ms 1125556 KB Output is correct
47 Correct 2465 ms 1125668 KB Output is correct
48 Correct 1815 ms 1125536 KB Output is correct
49 Correct 2865 ms 1125632 KB Output is correct
50 Correct 2134 ms 1125616 KB Output is correct
51 Correct 1467 ms 1125544 KB Output is correct
52 Correct 2078 ms 1125548 KB Output is correct
53 Correct 3948 ms 1125412 KB Output is correct
54 Correct 3075 ms 1125336 KB Output is correct
55 Correct 4062 ms 1125452 KB Output is correct
56 Correct 5518 ms 1125416 KB Output is correct
57 Correct 5589 ms 1125328 KB Output is correct
58 Correct 5498 ms 1125320 KB Output is correct
59 Correct 5283 ms 1125360 KB Output is correct
60 Correct 4983 ms 1125408 KB Output is correct
61 Correct 5005 ms 1125428 KB Output is correct