Submission #1019408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019408		aykhn	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	1204 ms	424988 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <assert.h>
#include <cstdio>
#define get_phase(x) min((63-__builtin_clzll(x)), maxphase-1)
#define win(node, phase) (get_phase(s[node]) < phase)
#define draw(node, phase) (get_phase(s[node]) == phase)
#define loc_out(x) (win(x, phase) ? w[x] : l[x])
#define sz_out(x) (win(x, phase) ? s[x] : p[x])

using namespace std;

const int maxphase = 25; // number of phases
const int maxpath = 25; // log2(maximum path length)
const int maxn = 4e5+5;
const long long inf = 1LL<<60;
int n;
vector<long long> s,p;
vector<int>w,l;

long long sze1[maxphase][maxn];
long long mx1[maxphase][maxn];
int loc1[maxphase][maxn];

long long sze2[maxpath][maxn];
long long mx2[maxpath][maxn];
int loc2[maxpath][maxn];

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
    n = _n; s = vector<long long>(begin(_s), end(_s)); p = vector<long long>(begin(_p), end(_p)); w = _w; l = _l;

    int dfs[n+1];
    int curr = 0;
    for(int phase=0; phase<maxphase; phase++) {
        // begin dfs to look for node with the correct phase
        for(int node=0; node<n; node++) {
            sze1[phase][node] = -1;
        }
        for(int node=0; node<n; node++) {
            if(sze1[phase][node] != -1) continue; // -1 for unvisited
            dfs[curr++] = node;
             do {
                sze1[phase][dfs[curr-1]] = -2;
                if(win(dfs[curr-1], phase)) {
                    dfs[curr] = w[dfs[curr-1]]; // win
                } else {
                    dfs[curr] = l[dfs[curr-1]]; // lose
                }
                curr++;
            } while(dfs[curr-1]!=n && sze1[phase][dfs[curr-1]] == -1 && !draw(dfs[curr-1], phase));

            if(dfs[curr-1]==n || draw(dfs[curr-1], phase)) {
                sze1[phase][dfs[curr-2]] = sz_out(dfs[curr-2]);
                mx1[phase][dfs[curr-2]] = win(dfs[curr-2], phase) ? inf : s[dfs[curr-2]];
                loc1[phase][dfs[curr-2]] = dfs[curr-1];
                for(int i=(int)curr-2; i>=1; i--) {
                    sze1[phase][dfs[i-1]] = min(sze1[phase][dfs[i]] + sz_out(dfs[i-1]), inf);
                    mx1[phase][dfs[i-1]] = min(win(dfs[i-1], phase) ? inf : s[dfs[i-1]],
                                               mx1[phase][dfs[i]] - sz_out(dfs[i-1]));
                    loc1[phase][dfs[i-1]] = loc1[phase][dfs[i]];
                }
            } else if(sze1[phase][dfs[curr-1]] >= 0) { // has a legit outgoing edge
                for(int i =(int) curr-1; i>=1; i--) {
                    sze1[phase][dfs[i-1]] = min(sze1[phase][dfs[i]] + sz_out(dfs[i-1]), inf);
                    mx1[phase][dfs[i-1]] = min(win(dfs[i-1], phase) ? inf : s[dfs[i-1]],
                                               mx1[phase][dfs[i]] - sz_out(dfs[i-1]));
                    loc1[phase][dfs[i-1]] = loc1[phase][dfs[i]];

                }
            }
            curr = 0;
        }
    }

    for(int node=0; node<n; node++) {
        sze2[0][node] = sze1[get_phase(s[node])][node];
        mx2[0][node] = mx1[get_phase(s[node])][node];
        loc2[0][node] = loc1[get_phase(s[node])][node];
    }

    sze2[0][n] = 0;
    mx2[0][n] = inf;
    loc2[0][n] = n;

    for(int len=1; len<maxpath; len++) {
        for(int node=0; node<=n; node++) {
            int l2 = loc2[len-1][node];
            if(l2!=-1) {
                sze2[len][node] = min(sze2[len-1][node] + sze2[len-1][l2],inf);
                mx2[len][node] = min(mx2[len-1][node],  mx2[len-1][l2]-sze2[len-1][node]);
                loc2[len][node] = loc2[len-1][l2];
            } else {
                sze2[len][node] = sze2[len-1][node];
                mx2[len][node] = mx2[len-1][node];
                loc2[len][node] = loc2[len-1][node];
            }
        }
    }
}

void step_forward(int &x, long long &z) {
    if(z >= s[x]) {
        z += s[x];
        x = w[x];
    } else {
        z += p[x];
        x = l[x];
    }
}

long long simulate(int x, int _z) {
    long long z = _z;
    int phase = get_phase(z);
    while(x<n) {
        assert(phase<maxphase);
        if(z < mx1[phase][x] && sze1[phase][x] != inf) {
            z += sze1[phase][x];
            x = loc1[phase][x];

            if(x==n) return z;
            for(int i=min(maxpath-1, 1+get_phase(s[x])); i>=0; i--) {
                if(z < mx2[i][x] && sze2[i][x] != inf) {
                    z += sze2[i][x];
                    x = loc2[i][x];
                }
            }
            if(x==n) return z;
            assert(z >= mx1[phase][x] || sze1[phase][x] == inf);
        }
        if (phase == get_phase(s[x])) {
            step_forward(x,z);
            phase = max(phase, get_phase(z));
        } else {
            phase++;
        }
    }
    return z;
}

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