제출 #1011818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011818		boris_mihov	던전 (IOI21_dungeons)	C++17	11 / 100	298 ms	396860 KiB

dungeons

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

typedef long long llong;
const int MAXN = 50000 + 10;
const int MAXNUMLOG = 25;
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];
    llong minimumZ[MAXNUMLOG][MAXN];

    void build(int log)
    {
        memset(next, -1, sizeof(next));
        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;
        sumJumps[0][n] = 0;
        minimumZ[0][n] = 0;
        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(minimumZ[lg - 1][i], 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)
        {
            assert(next[lg][node] != -1);
            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
        {
            z += loseGain[node];
            node = loseNext[node];
        }
    }
};

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: 11 / 11
• Subtask 2: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11