Submission #1237424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237424		Hamed_Ghaffari	던전 (IOI21_dungeons)	C++20	11 / 100	7110 ms	313524 KiB

dungeons

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MXN = 5e4+3, LOGS=24, LOGN=16;
const ll inf = 1e18;
const int inf32 = 1e9;

int n, s[MXN], p[MXN], w[MXN], l[MXN], f[LOGS+1][LOGN][MXN];
ll sum[LOGS+1][LOGN][MXN];
int mn[LOGS][LOGN][MXN];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    ::n = n;
    assert(n<=50000);
    for(int i=0; i<n; i++) {
        ::s[i] = s[i];
        ::p[i] = p[i];
        ::w[i] = w[i];
        ::l[i] = l[i];
    }
    for(int t=0; t<LOGS; t++) {
        for(int i=0; i<LOGN; i++) f[t][i][n] = n;
        for(int i=0; i<n; i++) {
            f[t][0][i] = (s[i]<(1<<t) ? w[i] : l[i]),
            sum[t][0][i] = (s[i]<(1<<t) ? s[i] : p[i]);
            mn[t][0][i] = ((1<<t)<=s[f[t][0][i]] && s[f[t][0][i]]<(1<<(t+1))
                ? max(0ll, s[f[t][0][i]]-sum[t][0][i])
                : inf32);
        }

        for(int i=1; i<LOGN; i++)
            for(int j=0; j<n; j++) {
                f[t][i][j] = f[t][i-1][f[t][i-1][j]];
                sum[t][i][j] = sum[t][i-1][j] + sum[t][i-1][f[t][i-1][j]];
                mn[t][i][j] = mn[t][i-1][f[t][i-1][j]]==inf32
                    ? mn[t][i-1][j]
                    : min(mn[t][i-1][j], (int)max(0ll, mn[t][i-1][f[t][i-1][j]]-sum[t][i-1][j]));
            }
    }
    for(int i=0; i<LOGN; i++) f[LOGS][i][n] = n;
    for(int i=0; i<n; i++) f[LOGS][0][i] = w[i], sum[LOGS][0][i] = s[i];
    for(int i=1; i<LOGN; i++)
        for(int j=0; j<n; j++)
            f[LOGS][i][j] = f[LOGS][i-1][f[LOGS][i-1][j]],
            sum[LOGS][i][j] = sum[LOGS][i-1][j] + sum[LOGS][i-1][f[LOGS][i-1][j]];
}

ll simulate(int x, int z) {
    ll ans=z;
    for(int t=0; t<LOGS; t++) if(ans<(1<<(t+1))) {
        if(!((1<<t)<=s[x] && s[x]<(1<<(t+1))) || s[x]>ans)
            for(int i=LOGN-1; i>=0; i--)
                if(f[t][i][x]!=n && ans+sum[t][i][x]<(1<<(t+1)) && (mn[t][i][x]==inf32 || mn[t][i][x]>ans)) {
                    ans += sum[t][i][x];
                    x = f[t][i][x];
                }
        while(ans<(1<<(t+1))) {
            if(ans>=s[x]) {
                ans += s[x];
                x = w[x];
            }
            else {
                ans += p[x];
                x = l[x];
            }
            if(x==n) return ans;
        }
    }
    if(x!=n) {
        for(int i=LOGN-1; i>=0; i--)
            if(f[LOGS][i][x]!=n) {
                ans += sum[LOGS][i][x];
                x = f[LOGS][i][x];
            }
        ans += sum[LOGS][0][x];
    }
    return ans;
}

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