Submission #1232885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232885		a4n_	Dungeons Game (IOI21_dungeons)	C++20	37 / 100	349 ms	258024 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 {
    ll dest, sump, mx;
    node() {
        dest = sump = mx = 0;
    }
} par[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=n+1; i>=1; i--) {
        par[0][i].dest = w[i];
        par[0][i].mx = s[i];
        par[0][i].sump = s[i];
        for(int j=1; j<lg; j++) {
            par[j][i].dest = par[j-1][par[j-1][i].dest].dest;
            par[j][i].sump = par[j-1][i].sump + par[j-1][par[j-1][i].dest].sump;
            par[j][i].mx = max(par[j-1][i].mx, par[j-1][par[j-1][i].dest].mx);
        }
    }
}


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 >= 1e7) return (ll)dp[x] + z;

        for(int i=lg-1; i>=0; i--) {
            if(z >= par[i][x].mx) {
                z += par[i][x].sump;
                x = par[i][x].dest;
            }
        }

        pii tmp = move(x, z);
        x = tmp.F, z = tmp.S;

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

    return z;
}

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