oj.uz

Submission #1011798

# Submission time Handle Problem Language Result Execution time Memory
1011798 2024-07-01T08:47:05 Z boris_mihov Dungeons Game (IOI21_dungeons) C++17
0 / 100
 6 ms 11612 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5468 KB Output is correct
2 Incorrect 2 ms 5696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11608 KB Output isn't correct
2 Halted 0 ms 0 KB -