Submission #606719

#	Time	Username	Problem	Language	Result	Execution time	Memory
606719		jiahng	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7024 ms	598180 KiB

dungeons

#include "dungeons.h"
#include <vector>

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 400010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int twokw[maxn][30], twokl[maxn][30], valw[maxn][30], vall[maxn][30], mnw[maxn][30], mxl[maxn][30];
int S[maxn], P[maxn], W[maxn], L[maxn];
int N;
void init(int32_t n, std::vector<int32_t> s, std::vector<int32_t> p, std::vector<int32_t> w, std::vector<int32_t> l) {
    N = n;
    FOR(i,0,N-1){
        S[i] = s[i], P[i] = p[i], W[i] = w[i], L[i] = l[i];
    }
    FOR(i,0,N-1){
        twokw[i][0] = w[i], twokl[i][0] = l[i];
        vall[i][0] = p[i], valw[i][0] = s[i];
        mxl[i][0] = s[i]-1, mnw[i][0] = s[i];
    }
    twokw[N][0] = twokl[N][0] = N;
    FOR(k,1,29){
        FOR(i,0,N){
           twokw[i][k] = twokw[twokw[i][k-1]][k-1];
           twokl[i][k] = twokl[twokl[i][k-1]][k-1]; 
          
           valw[i][k] = valw[i][k-1] + valw[twokw[i][k-1]][k-1];
           vall[i][k] = vall[i][k-1] + vall[twokl[i][k-1]][k-1];
            
           mnw[i][k] = max(mnw[i][k-1], mnw[twokw[i][k-1]][k-1] - valw[i][k-1]);
           mxl[i][k] = min(mxl[i][k-1], mxl[twokl[i][k-1]][k-1] - vall[i][k-1]);
        }
    }
	return;
}

long long simulate(int32_t x, int32_t z) {
    while (1){
        if (z >= S[x]){
            DEC(k,29,0) if (twokw[x][k] < N && z >= mnw[x][k]){
                //cout << k << ' ';
                z += valw[x][k];
                x = twokw[x][k];
            }
        }else{
            DEC(k,29,0) if (twokl[x][k] < N && z <= mxl[x][k]){
                //cout << k << ' ';
                z += vall[x][k];
                x = twokl[x][k];
            }
        }
        //cout << x << ' ' << z << '\n';
        if (z >= S[x] && W[x] == N) return z + S[x];
        if (z < S[x] && L[x] == N) return z + P[x];


    }
	return 0;
}

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