Submission #560271

#	Time	Username	Problem	Language	Result	Execution time	Memory
560271		nghiass001	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	7137 ms	1428144 KiB

dungeons

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#define MASK(i) (1LL << (i))
using namespace std;
const int N = 4e5 + 5, logM = 27;
const int N2 = 5e4 + 5;
const long long INF = 0x3c3c3c3c3c3c3c3c;

struct Data {
    int u;
    long long sum;
    long long smax;
    Data(int _u = -1, long long _sum = 0, long long _smax = 0) :
        u(_u), sum(_sum), smax(_smax) {};
};

int subtask;
int nn, lose[N], next_win[N], next_los[N];
long long strong[N];
long long pwin[N][logM], pwinmax[N][logM], sumwin[N][logM];
long long plos[N][logM], plosmin[N][logM], sumlos[N][logM];
Data pnext[logM + 1][N2][logM];
vector<long long> Q;

void init_2() {
    subtask = 2;
    REP(i, 0, nn) pwin[i][0] = next_win[i];
    FOR(i, 0, nn) {
        pwin[i][0] = next_win[i];
        plos[i][0] = next_los[i];
        pwinmax[i][0] = strong[i];
        plosmin[i][0] = strong[i];
        sumwin[i][0] = strong[i];
        sumlos[i][0] = lose[i];
    }

    REP(j, 1, logM) {
        FOR(i, 0, nn) {
            pwin[i][j] = pwin[pwin[i][j - 1]][j - 1];
            plos[i][j] = plos[plos[i][j - 1]][j - 1];
            pwinmax[i][j] = max(pwinmax[i][j - 1], pwinmax[pwin[i][j - 1]][j - 1] - sumwin[i][j - 1]);
            plosmin[i][j] = min(plosmin[i][j - 1], plosmin[plos[i][j - 1]][j - 1] - sumlos[i][j - 1]);
            sumwin[i][j] = sumwin[i][j - 1] + sumwin[pwin[i][j - 1]][j - 1];
            sumlos[i][j] = sumlos[i][j - 1] + sumlos[plos[i][j - 1]][j - 1];
        }
    }
}

void init_1345() {
    subtask = 1345;
    REP(i, 0, logM) Q.push_back(1 << i);
    Q.push_back(1e18);

    REP(i, 0, logM) {
        REP(j, 0, nn) {
            if (strong[j] < Q[i]) {
                pnext[i][j][0] = {next_win[j], strong[j], INF};
            }
            else if (strong[j] < Q[i + 1]) {
                pnext[i][j][0] = {next_los[j], lose[j], strong[j]};
            }
            else {
                pnext[i][j][0] = {next_los[j], lose[j], INF};
            }
        }
        REP(w, 0, logM - 1) REP(j, 0, nn) {
            if (pnext[i][j][w].u == -1) continue;
            int jnext = pnext[i][j][w].u;
            Data dnext = {
                pnext[i][jnext][w].u,
                pnext[i][j][w].sum + pnext[i][jnext][w].sum,
                min(pnext[i][j][w].smax, pnext[i][jnext][w].smax - pnext[i][j][w].sum)
            };
            pnext[i][j][w + 1] = dnext;
        }
    }
}

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    nn = n;
    REP(i, 0, nn) {
        strong[i] = s[i];
        lose[i] = p[i];
        next_win[i] = w[i];
        next_los[i] = l[i];
    }
    next_win[nn] = nn;
    next_los[nn] = nn;

    if (nn <= 50000) init_1345();
    else init_2();
}

long long simulate_sub2(int x, long long my_strong) {
    static bool WIN = 1, LOSE = 0;
    bool type = WIN;
    while (x != nn) {
        if (type == WIN) {
            REPD(i, logM, 0) {
                if (pwinmax[x][i] <= my_strong) {
                    my_strong += sumwin[x][i];
                    x = pwin[x][i];
                }
            }
            type = LOSE;
        }
        else if (type == LOSE) {
            REPD(i, logM, 0) {
                if (plosmin[x][i] > my_strong) {
                    my_strong += sumlos[x][i];
                    x = plos[x][i];
                }
            }
            type = WIN;
        }
    }
    return my_strong;
}

long long simulate_sub1345(int x, long long my_strong) {
    REP(i, 0, logM) {
        if (my_strong >= Q[i + 1]) continue;
        REPD(w, logM, 0) {
            Data dnow = pnext[i][x][w];
            if (dnow.u == -1) continue;
            if (my_strong + dnow.sum >= Q[i + 1]) continue;
            if (my_strong >= dnow.smax) continue;
            x = dnow.u;
            my_strong += dnow.sum;
        }

        if (x == nn) break;

        if (strong[x] <= my_strong) {
            my_strong += strong[x];
            x = next_win[x];
        }
        else {
            my_strong += lose[x];
            x = next_los[x];
        }

        assert(my_strong >= Q[i] * 2);
    }

    return my_strong;
}

long long simulate(int x, int my_strong) {
    if (subtask == 1345) return simulate_sub1345(x, my_strong);
    else return simulate_sub2(x, my_strong);
}

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