Submission #560454

#	Time	Username	Problem	Language	Result	Execution time	Memory
560454		nghiass001	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3025 ms	1804552 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)
using namespace std;
const int N = 4e5 + 5, logM = 28, limitSZ = logM * (logM + 1) / 2;
const int INF = 0x3c3c3c3c;

struct Data {
    int u;
    int sum;
    int smax;
};

int nn, lose[N], next_win[N], next_los[N], strong[N];
int go_nxt[N];
long long sum_end[N];

int num[logM + 1][logM];
Data pnext[limitSZ][N];
vector<long long> Q;

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;

    REP(i, 0, nn) go_nxt[i] = next_win[i], sum_end[i] = strong[i];
    go_nxt[nn] = nn;
    REP(i, 0, 19) {
        REP(j, 0, nn) {
            sum_end[j] += sum_end[go_nxt[j]];
            go_nxt[j] = go_nxt[go_nxt[j]];
        }
    }

    REP(i, 0, logM) Q.push_back(1 << i);

    int cnt = 0;
    REP(i, 0, logM) REP(j, 0, i) num[i][j] = cnt++;
    cerr << cnt;

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

long long simulate(int x, int my_strong) {
    REP(i, 0, logM) {
        if (my_strong >= Q[i + 1]) continue;
        REPD(j, i, 0) {
            int id = num[i][j];
            Data dnow = pnext[id][x];
            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 + sum_end[x];
}

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