Submission #523417

#	Time	Username	Problem	Language	Result	Execution time	Memory
523417		eecs	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3809 ms	1675384 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int B = 16, L = 7, INF = 0x3f3f3f3f;
const int maxn = 400005;
int n, lim[L], s[maxn], p[maxn], w[maxn], l[maxn];

struct node {
    int to; ll sum; int req;
    node operator + (const node b) const {
        return (node){b.to, sum + b.sum, b.req == INF ? req : max(0LL, min((ll)req, b.req - sum))};
    }
} f[L][25][maxn];

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
    n = _n, w[n] = l[n] = n;
    for (int i = 0; i < n; i++) {
        s[i] = _s[i], p[i] = _p[i], w[i] = _w[i], l[i] = _l[i];
    }
    auto init = [&](int X, node g[][maxn]) {
        for (int i = 0; i < n; i++) {
            g[0][i] = X >= s[i] ? node{w[i], s[i], INF} : node{l[i], p[i], s[i]};
        }
        for (int k = 1; k < 25; k++) {
            for (int i = 0; i < n; i++) {
                g[k][i] = g[k - 1][i] + g[k - 1][g[k - 1][i].to];
            }
        }
    };
    for (int d = 0; d < L; d++) {
        init(lim[d] = !d ? 1 : lim[d - 1] * B, f[d]);
    }
}

ll simulate(int x, int _z) {
    ll z = _z;
    int i = 0;
    while (x < n) {
        while (i + 1 < L && z >= lim[i + 1]) i++;
        for (int j = 24; ~j; j--) {
            if (f[i][j][x].to == n || f[i][j][x].req != INF && f[i][j][x].req <= z) continue;
            z += f[i][j][x].sum, x = f[i][j][x].to;
        }
        if (z >= s[x]) z += s[x], x = w[x];
        else z += p[x], x = l[x];
    }
    return z;
}

Compilation message (stderr)

dungeons.cpp: In member function 'node node::operator+(node) const':
dungeons.cpp:13:55: warning: narrowing conversion of '((((int)b.node::req) == ((int)INF)) ? ((long long int)((int)((const node*)this)->node::req)) : ((long long int)std::max<long long int>(0, (* & std::min<long long int>(((ll)((int)((const node*)this)->node::req)), (((long long int)((int)b.node::req)) - ((long long int)((const node*)this)->node::sum)))))))' from 'long long int' to 'int' [-Wnarrowing]
   13 |         return (node){b.to, sum + b.sum, b.req == INF ? req : max(0LL, min((ll)req, b.req - sum))};
      |                                          ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:43:61: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   43 |             if (f[i][j][x].to == n || f[i][j][x].req != INF && f[i][j][x].req <= z) continue;
      |                                       ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11