Submission #1237429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237429		Hamed_Ghaffari	Dungeons Game (IOI21_dungeons)	C++20	11 / 100	7108 ms	304516 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][LOGN][MXN];
ll sum[LOGS][LOGN][MXN], dp[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]));
            }
    }
    dp[n] = 0;
    for(int i=n-1; i>=0; i--)
        dp[i] = dp[w[i]] + s[i];
}

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;
        }
    }
    return ans + dp[x];
}

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