Submission #566453

#	Time	Username	Problem	Language	Result	Execution time	Memory
566453		kartel	Dungeons Game (IOI21_dungeons)	C++17	Compilation error	0 ms	0 KiB

dungeons

#include <bits/stdc++.h>
//#include "grader.cpp"
#include "dungeons.h"
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("-Ofast")
using namespace std;
typedef long long ll;

const int N = 4e5 + 2;
const int log2A = 25;
const int log8N = 7;

int up[N][log8N][log2A];
ll sum[N][log8N][log2A];
ll dp[N][log8N][log2A];
vector <int> s, w;
int n;

void init(int _n, vector <int> _s, vector <int> p, vector <int> _w, vector <int> l) {
    n = _n;
    s = _s; w = _w;
    for (int k = 0; k < log2A; k++) {
        for (int i = 0; i < n; i++) {
            if (s[i] <= (1 << k)) {
                up[i][0][k] = w[i];
                sum[i][0][k] = s[i];
                dp[i][0][k] = -4e18;
            } else {
                up[i][0][k] = l[i];
                sum[i][0][k] = p[i];
                dp[i][0][k] = -s[i];
            }
        }
        for (int st = 1; st < log4N; st++) {
            for (int i = 0; i < n; i++) {
                up[i][st][k] = up[i][st - 1][k];
                sum[i][st][k] = sum[i][st - 1][k];
                dp[i][st][k] = dp[i][st - 1][k];
                for (int j = 1; j < 8; j++) {
                    int to = up[i][st][k];
                    dp[i][st][k] = max(dp[i][st][k], dp[to][st - 1][k] + sum[i][st][k]);
                    sum[i][st][k] += sum[to][st - 1][k];
                    up[i][st][k] = up[to][st - 1][k];
                }
            }
        }
    }
}

ll simulate(int x, int start) {
    ll z = start;

    for (int k = 0; k < log2A && x != n; k++) {
        if (z >= (1 << (k + 1)) && k + 1 < log2A) {
            continue;
        }
        for (int j = log4N - 1; j >= 0 && x != n; j--) {
            for (int p = 0; p < 8 && x != n; p++) {
                if (z + dp[x][j][k] < 0) {
                    z += sum[x][j][k];
                    x = up[x][j][k];
                } else {
                    break;
                }
            }
        }
        if (x == n) {
            break;
        }
        z += s[x];
        x = w[x];
    }
//    assert(x == n);
    return z;
}

/*

3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3

*/

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:35:31: error: 'log4N' was not declared in this scope; did you mean 'log8N'?
   35 |         for (int st = 1; st < log4N; st++) {
      |                               ^~~~~
      |                               log8N
dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:58:22: error: 'log4N' was not declared in this scope; did you mean 'log8N'?
   58 |         for (int j = log4N - 1; j >= 0 && x != n; j--) {
      |                      ^~~~~
      |                      log8N