Submission #618956

#	Time	Username	Problem	Language	Result	Execution time	Memory
618956		happypotato	Dungeons Game (IOI21_dungeons)	C++17	36 / 100	7085 ms	91484 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 5e4 + 1;
vector<int> s, p, w, l;
int n;
int st;
// st34 initialize
int liftpar[6][mxN][25];
ll int liftsum[6][mxN][25];
vector<int> diffs = {0};
void ComputeLift() {
    for (int i = 0; i < int(diffs.size()); i++) {
        for (int u = 0; u < n; u++) {
            if (s[u] <= diffs[i]) {
                liftpar[i][u][0] = w[u];
                liftsum[i][u][0] = s[u];
            } else {
                liftpar[i][u][0] = l[u];
                liftsum[i][u][0] = p[u];
            }
        }
        for (int dep = 1; dep < 25; dep++) {
            for (int u = 0; u < n; u++) {
                if (liftpar[i][u][dep - 1] == n) {
                    liftpar[i][u][dep] = n;
                    liftsum[i][u][dep] = liftsum[i][u][dep - 1];
                } else {
                    liftpar[i][u][dep] = liftpar[i][liftpar[i][u][dep - 1]][dep - 1];
                    liftsum[i][u][dep] = liftsum[i][u][dep - 1] + liftsum[i][liftpar[i][u][dep - 1]][dep - 1];
                }
            }
        }
    }
}
void st34init() {
    for (int i = 0; i < n; i++) {
        bool appear = false;
        for (int &x : diffs) {
            appear |= (x == s[i]);
        }
        if (!appear) diffs.pb(s[i]);
    }
    sort(diffs.begin(), diffs.end());
    ComputeLift();
}
void init(int on, vector<int> os, vector<int> op, vector<int> ow, vector<int> ol) {
    n = on;
    s = os; p = op; w = ow; l = ol;
    bool isst2 = true;
    for (int i = 0; i < n; i++) {
        isst2 &= (s[i] == p[i]);
    }
    if (isst2) {
        st = 2;
        return;
    } else if (n > 50000) {
        st = 6;
        return;
    }
    set<int> dists;
    for (int i = 0; i < n; i++) {
        dists.insert(s[i]);
        if (dists.size() > 5) break;
    }
    if (dists.size() <= 5) {
        st = 4;
        st34init();
        return;
    }
    // 1 and 5 is ???
    st = 1;
    return;
}
ll int st1(int x, ll int z) {
    while (x != n) {
        if (z >= s[x]) {
            z += s[x];
            x = w[x];
        } else {
            z += p[x];
            x = l[x];
        }
    }
    return z;
}
ll int st2(int x, ll int z) {
    return 0;
}
ll int st34(int x, ll int z) {
    for (int i = 0; i < int(diffs.size()); i++) {
        ll int tar = (i == int(diffs.size()) - 1 ? 1e18 : diffs[i + 1]);
        if (z >= tar) continue;
        for (int dep = 24; dep >= 0; dep--) {
            if (z + liftsum[i][x][dep] < tar) {
                z += liftsum[i][x][dep];
                x = liftpar[i][x][dep];
                if (x == n) return z;
            }
        }
        z += liftsum[i][x][0];
        x = liftpar[i][x][0];
        if (x == n) return z;
    }
    return -1;
}
long long simulate(int x, int z) {
    if (st == 1) return st1(x, z);
    if (st == 2) return st2(x, z);
    if (st == 3 || st == 4) return st34(x, z);
    return 0;
}

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