Submission #1210343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210343		badge881	Dungeons Game (IOI21_dungeons)	C++20	100 / 100	5929 ms	1931292 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()

using namespace std;

int N;
vector<int> s, p, w, l;
vector<int> ss;
vector<vector<vector<pair<int, pair<int, int>>>>> nxt;
vector<long long> tw;

const int LOG = 22;
const int MAXS = 1e7;
int sn;

long long pth(int x)
{
    if (x == N)
        return 0;
    if (tw[x] >= 0)
        return tw[x];
    tw[x] = pth(w[x]) + (long long)s[x];
    return tw[x];
}

void init(signed n, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L)
{
    N = n;
    s.resize(N);
    tw.resize(N, -1);
    p.resize(N);
    w.resize(N + 1);
    l.resize(N + 1);
    l[N] = N;
    w[N] = N;
    for (int i = 0; i < n; i++)
    {
        s[i] = S[i];
        p[i] = P[i];
        w[i] = W[i];
        l[i] = L[i];
    }
    ss.push_back(0);
    int u = 1;
    ss.push_back(u);
    while (u < MAXS)
    {
        u *= 6;
        ss.push_back(u);
    }
    sn = sz(ss);
    nxt.resize(N + 1, vector<vector<pair<int, pair<int, int>>>>(sn, vector<pair<int, pair<int, int>>>(1, {0, {0, 0}})));

    for (int j = 0; j < sz(ss); j++)
    {
        nxt[N][j][0].first = 0;
        nxt[N][j][0].second.first = N;
        nxt[N][j][0].second.second = 1e8;
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < sz(ss); j++)
        {
            if (s[i] <= ss[j])
            {
                nxt[i][j][0].first = s[i];
                nxt[i][j][0].second.first = w[i];
                nxt[i][j][0].second.second = 1e8;
            }
            else
            {
                nxt[i][j][0].first = p[i];
                nxt[i][j][0].second.first = l[i];
                nxt[i][j][0].second.second = s[i];
            }
        }
    }
    for (int j = 1; j < LOG; j++)
    {
        for (int i = 0; i <= N; i++)
        {
            for (int k = 0; k < sz(ss); k++)
            {
                if (j > sz(nxt[i][k]) || nxt[i][k][j - 1].second.first == N || j > sz(nxt[nxt[i][k][j - 1].second.first][k]) || nxt[i][k][j - 1].second.second <= ss[k] || nxt[nxt[i][k][j - 1].second.first][k][j - 1].second.second - nxt[i][k][j - 1].first <= ss[k])
                    continue;
                nxt[i][k].push_back({nxt[i][k][j - 1].first + nxt[nxt[i][k][j - 1].second.first][k][j - 1].first, {nxt[nxt[i][k][j - 1].second.first][k][j - 1].second.first, min(nxt[i][k][j - 1].second.second, nxt[nxt[i][k][j - 1].second.first][k][j - 1].second.second - nxt[i][k][j - 1].first)}});
            }
        }
    }
    return;
}

int cs, u;

long long simulate(signed x, signed z)
{
    cs = z;
    u = x;
    for (int i = 0; i < sz(ss); i++)
    {
        while (ss[i + 1] > cs)
        {
            for (int j = LOG - 1; j >= 0; j--)
            {
                if (j >= sz(nxt[u][i]) || nxt[u][i][j].second.first == N || nxt[u][i][j].second.second <= cs)
                    continue;
                cs += nxt[u][i][j].first;
                u = nxt[u][i][j].second.first;
            }
            if (nxt[u][i][0].second.first == N)
            {
                if (s[u] > cs)
                    cs += p[u];
                else
                    cs += s[u];
                return cs;
            }
            else
            {
                if (s[u] > cs)
                    cs += p[u],
                    u = l[u];
                else
                    cs += s[u],
                        u = w[u];
            }
            if (u == N)
                return cs;
        }
    }
    return (long long)cs + pth(u);
}

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