제출 #1237470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237470		Hamed_Ghaffari	Dungeons Game (IOI21_dungeons)	C++20	63 / 100	1885 ms	388152 KiB

dungeons

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int MXN = 5e4 + 10, LOG = 25, inf = 1e7;
 
int t, n, s[MXN], p[MXN], w[MXN], l[MXN];
ll dp[MXN];

struct node {
    int f, sum, mn;
    node(): f(0), sum(0), mn(0) {}
} par[LOG][LOG][MXN];

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
    n = _n;
    for(int i=1; i<=n; i++)
        s[i] = _s[i-1], p[i] = _p[i-1], w[i] = _w[i-1] + 1, l[i] = _l[i-1] + 1;
    w[n + 1] = n + 1;
    l[n + 1] = n + 1;
    for(int i=n; i>=1; i--)
        dp[i] = dp[w[i]] + s[i];

    for(int i=1; i<=n+1; i++)
        for(int j=0; j<LOG; j++)
            if(s[i] < (1<<j)) {
                par[0][j][i].f = w[i];
                par[0][j][i].mn = inf;
                par[0][j][i].sum = s[i];
            } 
            else {
                par[0][j][i].f = l[i];
                par[0][j][i].mn = s[i] - 1;
                par[0][j][i].sum = p[i];
            }

    for(int i=1; i<LOG; i++)
        for(int j=0; j<LOG; j++)
            for(int k=1; k<=n+1; k++) {
                par[i][j][k].f = par[i-1][j][par[i-1][j][k].f].f;
                par[i][j][k].mn = min(par[i-1][j][k].mn, par[i-1][j][par[i-1][j][k].f].mn - par[i-1][j][k].sum);
                par[i][j][k].sum = par[i-1][j][k].sum + par[i-1][j][par[i-1][j][k].f].sum;
            }
}

ll simulate(int x, int z) {
    x++;
    while(x <= n && z <= 64) {
        if(z>=s[x]) {
            z += s[x];
            x = w[x];
        }
        else {
            z += p[x];
            x = l[x];
        }
    }
    while(x <= n) {
        int t = min(__lg(z), LOG - 1);
        for(int i=t; i>=0; i--) {
            if(z <= par[i][t][x].mn) {
                z += par[i][t][x].sum;
                x = par[i][t][x].f;
            }
        }
        if(z>=s[x]) {
            z += s[x];
            x = w[x];
        }
        else {
            z += p[x];
            x = l[x];
        }
        if(z >= inf) return (ll)dp[x] + z;
    }
    return z;
}

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