제출 #1290295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290295		mariaclara	던전 (IOI21_dungeons)	C++17	100 / 100	2411 ms	1519848 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int MAXN = 4e5+5, C = 10, lC = 8;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int N, nxt[lC][24][MAXN];
ll sum[lC][24][MAXN], mind[lC][24][MAXN];
// mind = min(s - sum)
vi S, W;

void init(int n, vi s, vi p, vi w, vi l) {
    N = n;
    S = s;
    W = w;

    for(int R = 0, pot = 1; R < lC and pot <= 1e7; pot *= C, R++) {
        // pot, pot*C-1
        nxt[R][0][n] = n;
        mind[R][0][n] = 1e18;

        for(int i = 0; i < n; i++) {
            if(s[i] <= pot) nxt[R][0][i] = w[i], sum[R][0][i] = s[i], mind[R][0][i] = 1e18;
            else nxt[R][0][i] = l[i], sum[R][0][i] = p[i], mind[R][0][i] = s[i];
        }

        for(int b = 1; b < 24; b++) {
            for(int i = 0; i <= n; i++) {
                nxt[R][b][i] = nxt[R][b-1][nxt[R][b-1][i]];
                sum[R][b][i] = sum[R][b-1][i] + sum[R][b-1][nxt[R][b-1][i]];
                mind[R][b][i] = min(mind[R][b-1][i], mind[R][b-1][nxt[R][b-1][i]] - sum[R][b-1][i]);
            }
        }
    }
}

ll simulate(int x, int aux) {
    int R = 0;
    ll z = aux, pot = 1;

    while(x != N) {
        while(R < lC - 1 and pot*C <= z) R++, pot *= C;

        for(int b = 23; b >= 0; b--)
            if(mind[R][b][x] > z) z += sum[R][b][x], x = nxt[R][b][x];

        if(x == N) return z;

        z += S[x];
        x = W[x];
    }

    return z;
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11