Submission #1232881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232881		a4n_	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	102 ms	235328 KiB

dungeons

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 4e5 + 100, lg = 25;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
int t, n, s[N], p[N], w[N], l[N];
ll dp[N];

struct node {
    int dest, sump, mx;
    node() {
        dest = sump = mx = 0;
    }
} par[2][lg][N];

pii move(int x, int z) {
    if(z >= s[x]) return {w[x], z + s[x]};
    return {l[x], z + p[x]};
}

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<1; j++) {
            if(s[i] < (1<<s[1])) {
                par[0][j][i].dest = w[i];
                par[0][j][i].mx = 1e7;
                par[0][j][i].sump = s[i];
            } else {
                par[0][j][i].dest = l[i];
                par[0][j][i].mx = s[i] - 1;
                par[0][j][i].sump = p[i];
            }
        }
    }

    for(int i=1; i<lg; i++) {
        for(int j=0; j<1; j++) {
            for(int k=1; k<=n+1; k++) {

                par[i][j][k].dest = par[i-1][j][par[i-1][j][k].dest].dest;
par[i][j][k].mx = min(par[i-1][j][k].mx, par[i-1][j][par[i-1][j][k].dest].mx - par[i-1][j][k].sump);
par[i][j][k].sump = par[i-1][j][k].sump + par[i-1][j][par[i-1][j][k].dest].sump;

            }
        }
    }
}


long long simulate(int x, int z) {
    x ++;
    while(x <= n && z <= 256) {
        pii tmp = move(x, z);
        x = tmp.F, z = tmp.S;
    }
    while(x <= n) {
        if(z >= s[1]) return (ll)dp[x] + z;
        int wh = min(__lg(z), lg - 1);
        wh = 0;
        for(int i=lg-1; i>=0; i--) {
            if(z <= par[i][wh][x].mx) {
                z += par[i][wh][x].sump;
                x = par[i][wh][x].dest;
            }
        }
        pii tmp = move(x, z);
        x = tmp.F, z = tmp.S;

        if(z >= s[1]) return (ll)dp[x] + z;
        // if(__lg(z) == )
    }

    return z;
}

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