Submission #1011798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011798		boris_mihov	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	6 ms	11612 KiB

dungeons

#include "dungeons.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 50000 + 10;
const int MAXNUMLOG = 24;
const int MAXLOG = 16;
const int INF  = 1e9;

namespace
{
    int n;
    int h[MAXN];
    int winNext[MAXN];
    int loseNext[MAXN];
    int loseGain[MAXN];
}

struct Sparse
{
    int next[MAXNUMLOG][MAXN];
    llong sumJumps[MAXNUMLOG][MAXN];
    int minimumZ[MAXNUMLOG][MAXN];

    void build(int log)
    {
        for (int i = 0 ; i < n ; ++i)
        {
            if (h[i] <= (1 << log))
            {
                next[0][i] = winNext[i];
                sumJumps[0][i] = h[i];
                minimumZ[0][i] = INF;
            } else
            {
                next[0][i] = loseNext[i];
                sumJumps[0][i] = loseGain[i];
                minimumZ[0][i] = h[i];
            }
        }

        next[0][n] = n;
        for (int lg = 1 ; lg < MAXNUMLOG ; ++lg)
        {
            for (int i = 0 ; i < n ; ++i)
            {
                next[lg][i] = next[lg - 1][next[lg - 1][i]];
                sumJumps[lg][i] = sumJumps[lg - 1][i] + sumJumps[lg - 1][next[lg - 1][i]];
                minimumZ[lg][i] = std::min((llong)minimumZ[lg - 1][i], (llong)minimumZ[lg - 1][next[lg - 1][i]] - sumJumps[lg - 1][i]);
            }
        }
    }

    void simulate(int &node, llong &z)
    {
        for (int lg = MAXNUMLOG - 1 ; lg >= 0 ; --lg)
        {
            if (next[lg][node] == n || z >= minimumZ[lg][node])
            {
                continue;
            }

            z += sumJumps[lg][node];
            node = next[lg][node];
        }

        if (z >= h[node])
        {
            z += h[node];
            node = winNext[node];
        } else
        {
            assert(false);
        }
    }
};

Sparse sparse[MAXNUMLOG];

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l)
{
    ::n = n;
    for (int i = 0 ; i < n ; ++i)
    {
        h[i] = s[i];
        winNext[i] = w[i];
        loseNext[i] = l[i];
        loseGain[i] = p[i];
    }

    for (int i = 0 ; i < MAXLOG ; ++i)
    {
        sparse[i].build(i);
    }

	return;
}

long long simulate(int X, int Z) 
{
    llong z = Z;
    int node = X;
    for (int i = 0 ; i < MAXNUMLOG ; ++i)
    {
        sparse[i].simulate(node, z);
        if (node == n)
        {
            break;
        }
    }
    
	return z;
}

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