oj.uz

Submission #1011832

# Submission time Handle Problem Language Result Execution time Memory
1011832 2024-07-01T09:16:32 Z boris_mihov Dungeons Game (IOI21_dungeons) C++17
11 / 100
 7000 ms 396368 KB 
#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 llong INF = 4e18;
const int MAXLOG = 16;

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];
                if (log == MAXNUMLOG - 1) minimumZ[0][i] = INF;
                else 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]);
                if (log == MAXNUMLOG - 1) minimumZ[lg][i] = INF;
            }
        }
    }

    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;
}

llong 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;
        }

        assert(z >= (1 << i + 1));
    }

    while (node != n)
    {
        sparse[MAXNUMLOG - 1].simulate(node, z);
    }
    
	return z;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from dungeons.cpp:5:
dungeons.cpp: In function 'llong simulate(int, int)':
dungeons.cpp:123:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  123 |         assert(z >= (1 << i + 1));
      |                           ~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 82512 KB Output is correct
2 Correct 30 ms 82524 KB Output is correct
3 Correct 36 ms 94900 KB Output is correct
4 Correct 198 ms 394068 KB Output is correct
5 Correct 39 ms 95060 KB Output is correct
6 Correct 199 ms 394108 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 88756 KB Output is correct
2 Runtime error 97 ms 14416 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 88664 KB Output is correct
2 Correct 324 ms 394976 KB Output is correct
3 Execution timed out 7045 ms 396368 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 88664 KB Output is correct
2 Correct 324 ms 394976 KB Output is correct
3 Execution timed out 7045 ms 396368 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 88664 KB Output is correct
2 Correct 324 ms 394976 KB Output is correct
3 Execution timed out 7045 ms 396368 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 88756 KB Output is correct
2 Runtime error 97 ms 14416 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -