Submission #499569

#	Time	Username	Problem	Language	Result	Execution time	Memory
499569		blue	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	5299 ms	974012 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;

const int maxN = 400'000;
const int logN = 25;
const int logS = 8;

int N;
vector<int> S;
vector<int> P;
vector<int> W;
vector<int> L;

int nxt[1+maxN][logS][logN];
int gain[1+maxN][logS][logN];
int min_change[1+maxN][logS][logN]; //i, k, e

const int B = 10;
const int logMX = 25;
long long powB[1+logMX];

vector<long long> winscore(1+maxN, 0LL);

void tle_assert(bool b)
{
    if(!b) while(1);
}

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
    s.push_back(0);
    p.push_back(0);
    w.push_back(n);
    l.push_back(n);

    N = n;
    S = s;
    P = p;
    W = w;
    L = l;

    powB[0] = 1;
    for(int e = 1; e <= logMX; e++)
        powB[e] = B * powB[e-1];


    for(int i = 0; i <= N; i++)
    {
        for(int k = 0; k < logS; k++)
        {
            if(s[i] < powB[k])
            {
                nxt[i][k][0] = w[i];
                gain[i][k][0] = s[i];
                min_change[i][k][0] = powB[k+1] - gain[i][k][0];
            }
            else if(powB[k] <= s[i] && s[i] < powB[k+1])
            {
                nxt[i][k][0] = l[i];
                gain[i][k][0] = p[i];
                min_change[i][k][0] = min(powB[k+1] - p[i], (long long)s[i]);
            }
            else if(powB[k] < s[i])
            {
                nxt[i][k][0] = l[i];
                gain[i][k][0] = p[i];
                min_change[i][k][0] = powB[k+1] - gain[i][k][0];
            }
        }
    }

    for(int e = 1; e < logN; e++)
    {
        for(int i = 0; i <= N; i++)
        {
            for(int k = 0; k < logS; k++)
            {
                nxt[i][k][e] = nxt[ nxt[i][k][e-1] ][k][e-1];
                gain[i][k][e] = gain[i][k][e-1] + gain[ nxt[i][k][e-1] ][k][e-1];
                min_change[i][k][e] = min(min_change[i][k][e-1], min_change[ nxt[i][k][e-1] ][k][e-1] - gain[i][k][e-1]);
            }
        }
    }

    for(int i = N-1; i >= 0; i--)
        winscore[i] = winscore[ W[i] ] + S[i];
}

long long simulate(int x, int z)
{
    int X = x;
    long long Z = z;
    for(int k = 0; k < logS; k++)
    {
        for(int T = 1; T <= B-1; T++)
        {
            if(powB[k+1] <= Z) continue;

            for(int e = logN - 1; e >= 0; e--)
            {
                if(Z >= min_change[X][k][e]) continue;
                Z += gain[X][k][e];
                X = nxt[X][k][e];
            }

            if(Z >= S[X])
            {
                Z += S[X];
                X = W[X];
            }
            else
            {
                Z += P[X];
                X = L[X];
            }
        }
    }

    Z += winscore[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