oj.uz

Submission #1011834

# Submission time Handle Problem Language Result Execution time Memory
1011834 2024-07-01T09:17:52 Z boris_mihov Dungeons Game (IOI21_dungeons) C++17
63 / 100
 1420 ms 616920 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 < MAXNUMLOG ; ++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));
    }

    assert(node == n);
	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 51 ms 128636 KB Output is correct
2 Correct 55 ms 128744 KB Output is correct
3 Correct 62 ms 148308 KB Output is correct
4 Correct 298 ms 614364 KB Output is correct
5 Correct 61 ms 148304 KB Output is correct
6 Correct 290 ms 614224 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 138320 KB Output is correct
2 Runtime error 92 ms 14408 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 138320 KB Output is correct
2 Correct 390 ms 615140 KB Output is correct
3 Correct 743 ms 615260 KB Output is correct
4 Correct 356 ms 616276 KB Output is correct
5 Correct 384 ms 616240 KB Output is correct
6 Correct 412 ms 616512 KB Output is correct
7 Correct 403 ms 616276 KB Output is correct
8 Correct 337 ms 616016 KB Output is correct
9 Correct 322 ms 616016 KB Output is correct
10 Correct 313 ms 615868 KB Output is correct
11 Correct 313 ms 616280 KB Output is correct
12 Correct 806 ms 616512 KB Output is correct
13 Correct 316 ms 616272 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 138320 KB Output is correct
2 Correct 390 ms 615140 KB Output is correct
3 Correct 743 ms 615260 KB Output is correct
4 Correct 356 ms 616276 KB Output is correct
5 Correct 384 ms 616240 KB Output is correct
6 Correct 412 ms 616512 KB Output is correct
7 Correct 403 ms 616276 KB Output is correct
8 Correct 337 ms 616016 KB Output is correct
9 Correct 322 ms 616016 KB Output is correct
10 Correct 313 ms 615868 KB Output is correct
11 Correct 313 ms 616280 KB Output is correct
12 Correct 806 ms 616512 KB Output is correct
13 Correct 316 ms 616272 KB Output is correct
14 Correct 55 ms 138832 KB Output is correct
15 Correct 403 ms 616652 KB Output is correct
16 Correct 408 ms 616768 KB Output is correct
17 Correct 482 ms 616256 KB Output is correct
18 Correct 476 ms 616220 KB Output is correct
19 Correct 388 ms 616512 KB Output is correct
20 Correct 446 ms 616024 KB Output is correct
21 Correct 482 ms 616280 KB Output is correct
22 Correct 293 ms 616140 KB Output is correct
23 Correct 340 ms 616276 KB Output is correct
24 Correct 712 ms 616516 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 138320 KB Output is correct
2 Correct 390 ms 615140 KB Output is correct
3 Correct 743 ms 615260 KB Output is correct
4 Correct 356 ms 616276 KB Output is correct
5 Correct 384 ms 616240 KB Output is correct
6 Correct 412 ms 616512 KB Output is correct
7 Correct 403 ms 616276 KB Output is correct
8 Correct 337 ms 616016 KB Output is correct
9 Correct 322 ms 616016 KB Output is correct
10 Correct 313 ms 615868 KB Output is correct
11 Correct 313 ms 616280 KB Output is correct
12 Correct 806 ms 616512 KB Output is correct
13 Correct 316 ms 616272 KB Output is correct
14 Correct 55 ms 138832 KB Output is correct
15 Correct 403 ms 616652 KB Output is correct
16 Correct 408 ms 616768 KB Output is correct
17 Correct 482 ms 616256 KB Output is correct
18 Correct 476 ms 616220 KB Output is correct
19 Correct 388 ms 616512 KB Output is correct
20 Correct 446 ms 616024 KB Output is correct
21 Correct 482 ms 616280 KB Output is correct
22 Correct 293 ms 616140 KB Output is correct
23 Correct 340 ms 616276 KB Output is correct
24 Correct 712 ms 616516 KB Output is correct
25 Correct 281 ms 615752 KB Output is correct
26 Correct 427 ms 616776 KB Output is correct
27 Correct 404 ms 616184 KB Output is correct
28 Correct 367 ms 616256 KB Output is correct
29 Correct 435 ms 616920 KB Output is correct
30 Correct 482 ms 616276 KB Output is correct
31 Correct 545 ms 616016 KB Output is correct
32 Correct 684 ms 616400 KB Output is correct
33 Correct 843 ms 616304 KB Output is correct
34 Correct 1420 ms 616296 KB Output is correct
35 Correct 738 ms 616140 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 138320 KB Output is correct
2 Runtime error 92 ms 14408 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -