Submission #618972

#	Time	Username	Problem	Language	Result	Execution time	Memory
618972		SlavicG	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7117 ms	589876 KiB

dungeons

#include "dungeons.h"
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
const int N = 4e5 + 10, K = 30;
pair<ll, ll> jump_win[N][K], jump_lose[N][K];
ll sum_win[N][K];
ll sum_lose[N][K];
ll finish, S[N], P[N], W[N], L[N];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    for(int i = 0; i < n; ++i) {
        S[i] = s[i], P[i] = p[i], W[i] = w[i], L[i] = l[i];
    }
    finish = n;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < K; ++j) {
            jump_win[i][j] = {n, 1e17};
            jump_lose[i][j] = {n, 0};
        }
    }
    for(int i = 0; i < n; ++i) {
        jump_win[i][0] = {w[i], s[i]};
        sum_win[i][0] = s[i];

        sum_lose[i][0] = p[i];
        jump_lose[i][0] = {l[i], s[i]};
    }
    for(int j = 1; j < K; ++j) {
        for(int i = 0; i < n; ++i) {
            jump_win[i][j].first = jump_win[jump_win[i][j - 1].first][j - 1].first;
            sum_win[i][j] = sum_win[i][j - 1] + sum_win[jump_win[i][j - 1].first][j - 1];
            ll need1 = jump_win[i][j - 1].second;
            ll need2 = jump_win[jump_win[i][j - 1].first][j - 1].second - sum_win[i][j - 1];
            jump_win[i][j].second = max(need1, need2);

            jump_lose[i][j].first = jump_lose[jump_lose[i][j - 1].first][j - 1].first;
            sum_lose[i][j] = sum_lose[i][j - 1] + sum_lose[jump_lose[i][j - 1].first][j - 1];
            need1 = jump_lose[i][j - 1].second;
            need2 = jump_lose[jump_lose[i][j - 1].first][j - 1].second - sum_lose[i][j - 1];
            jump_lose[i][j].second = min(need1, need2);
        }
    }
}

long long simulate(int x, int z) {
    ll w = z;
    while(x < finish) {
        for(int j = K - 1; j >= 0; --j) {
            if(w >= jump_win[x][j].second) {
                w += sum_win[x][j];
                x = jump_win[x][j].first;
            }
        }
        if(x == finish) break;
        for(int j = K - 1; j >= 0; --j) {
            if(w < jump_lose[x][j].second) {
                w += sum_lose[x][j];
                x = jump_lose[x][j].first;
            }
        }
    }
    return w;
}

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