Submission #1068173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068173		RaresFelix	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3499 ms	1609704 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

using namespace std;

using vi = vector<int>;
using ll = long long;

const int B = 4;
const int C = 3;
const int MPB = 14; /// log(MV) / log(B)
const int MK = 12; /// log(N) / log(C)
const int MN = 400000;

const int MV = 5e7;
const ll INF = 1e18;

struct salt {
    int u; // in ce nod am ajuns
    ll delta, smax;

    salt operator+(const salt &rhs) {
        salt re; /// prima data fac eu, dupa rhs
        if(smax == INF && rhs.smax == INF) re.smax = INF;
        else
            re.smax = min(smax, rhs.smax - delta);
        re.delta = rhs.delta + delta;
        re.u = rhs.u;
        return re;
    }
};

salt DP[MN][MPB][MK];
int n;
vi s, delta_l, w, l;

void init(int n0, vi s0, vi delta_l0, vi w0, vi l0) {
    n = n0;
    s = s0; delta_l = delta_l0; w = w0; l = l0;
    ll pow = 1;
    for(int p = 0; p < MPB; ++p) {
        ///pow... pow * B - 1
        for(int i = 0; i < n; ++i) {
            if(s[i] <= pow) {
                DP[i][p][0] = salt{w[i], s[i], INF};
            } else {
                DP[i][p][0] = salt{l[i], delta_l[i], s[i] - 1};
            }
        }
        for(int k = 1; k < MK; ++k) {
            /// C ^ k e saltul
            for(int i = 0; i < n; ++i) {
                salt eu = DP[i][p][k - 1];
                for(int j = 1; j < C; ++j) {
                    if(eu.u == n) break;
                    salt nou = DP[eu.u][p][k - 1];
                    eu = eu + nou;
                }
                DP[i][p][k] = eu;
            }
        }
        pow *= B;
    }
	return;
}

int nr_op = 0;
int nr_run = 0;
ll simulate(int x, int z0) {
    ++nr_run;
    ll p = 0, pow = 1;
    ll z = z0;
    while(x < n) {
        while(p + 1 < MPB && pow * B <= min(z, (ll)MV)) {
            ++p; pow *= B;
        }
        for(int k = MK - 1; k >= 0; --k) {
            while(x < n) {  /// max C ori rulata
                ++nr_op;
                salt eu = DP[x][p][k];
                if(eu.smax < z) break;
                x = eu.u;
                z += eu.delta;
            }
            if(x == n) break;
        }
        if(x == n) break;
        if(z >= s[x]) {
            z += s[x];
            x = w[x];
        } else {
            z += delta_l[x];
            x = l[x];
        }
    }
	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