Submission #438280

#	Time	Username	Problem	Language	Result	Execution time	Memory
438280		SHZhang	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	7093 ms	632648 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long

int n;
ll s[400005];
ll p[400005];
int w[400005], l[400005];
// lvl i => [2^i, 2^(i+1))

int f[24][24][50005]; // in level i tree, node arrived at after 2^j moves from k
ll g[24][24][50005]; // in level i tree, strength gained by 2^j moves from k
ll h[24][24][50005]; // in level i tree, min init strength to win against opponent in
                      // current level after at most 2^j moves from k

ll upval[24][400005];
int upnode[24][400005];

vector<int> tree[400005];

ll ssum[400005];

int block[10000005];

int f2[19][400005]; // 2^i ancestor
ll g2[19][400005]; // 2^i total strength
ll h2[19][400005]; // min strength needed to not lose after 2^i

bool mode2;

void predfs(int node)
{
    if (node != n + 1) {
        ssum[node] = ssum[w[node]] + s[node];
    }
    for (int i = 0; i < tree[node].size(); i++) {
        predfs(tree[node][i]);
    }
}

void dfs(int node, int lvl, int bound)
{
    if (node == n + 1 || s[node] >= bound) {
        upval[lvl][node] = 0;
        upnode[lvl][node] = node;
    } else {
        upval[lvl][node] = upval[lvl][w[node]] + s[node];
        upnode[lvl][node] = upnode[lvl][w[node]];
    }
    for (int i = 0; i < tree[node].size(); i++) {
        dfs(tree[node][i], lvl, bound);
    }
}

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
    for (int i = 0; i < 24; i++) {
        for (int j = (1 << i); j < min(1 << (i + 1), 10000001); j++) {
            block[j] = i;
        }
    }
    n = N;
    for (int i = 0; i < n; i++) {
        s[i+1] = S[i];
        p[i+1] = P[i];
        w[i+1] = W[i] + 1;
        l[i+1] = L[i] + 1;
    }
    for (int i = 1; i <= n; i++) {
        tree[w[i]].push_back(i);
    }
    predfs(n+1);
    mode2 = (n > 50000);
    if (mode2) {
        w[n+1] = n+1;
        for (int i = 1; i <= n + 1; i++) {
            f2[0][i] = w[i];
            g2[0][i] = s[i];
            h2[0][i] = s[i];
        }
        for (int pwr = 1; pwr < 19; pwr++) {
            for (int i = 1; i <= n + 1; i++) {
                f2[pwr][i] = f2[pwr-1][f2[pwr-1][i]];
                g2[pwr][i] = g2[pwr-1][i] + g2[pwr-1][f2[pwr-1][i]];
                h2[pwr][i] = max(h2[pwr-1][i], h2[pwr-1][f2[pwr-1][i]] - g2[pwr-1][i]);
            }
        }
        //fprintf(stderr, "HERE");
        return;
    }
    for (int lvl = 0; lvl < 24; lvl++) {
        dfs(n + 1, lvl, (1 << lvl));
        for (int i = 1; i <= n; i++) {
            if (s[i] < (1 << lvl)) continue;
            f[lvl][0][i] = upnode[lvl][l[i]];
            g[lvl][0][i] = p[i] + upval[lvl][l[i]];
            h[lvl][0][i] = s[i];
        }
        for (int pwr = 1; pwr < 24; pwr++) {
            for (int i = 1; i <= n; i++) {
                if (s[i] < (1 << lvl)) continue;
                int half = f[lvl][pwr-1][i];
                f[lvl][pwr][i] = f[lvl][pwr-1][half];
                g[lvl][pwr][i] = g[lvl][pwr-1][i] + g[lvl][pwr-1][half];
                h[lvl][pwr][i] = min(h[lvl][pwr-1][i],
                    h[lvl][pwr-1][half] - g[lvl][pwr-1][i]);
            }
        }
    }
}

long long simulate(int x, int Z) {
    x++;
    if (mode2) {
        ll curs = Z;
        while (true) {
            //fprintf(stderr, "%d %lld\n", x, curs);
            if (x == n + 1) return curs;
            if (curs < s[x]) {
                curs += p[x];
                x = l[x];
                //if (x == 0) return 123;
                continue;
            }
            for (int i = 18; i >= 0; i--) {
                if (curs >= h2[i][x]) {
                    curs += g2[i][x];
                    x = f2[i][x];
                }
                //if (x == 0) return 456;
                if (x == n + 1) return curs;
            }
        }
    }
    ll cur_s = Z;
    while (true) {
        if (x == n + 1) return cur_s;
        if (cur_s > 10000000) {
            cur_s += ssum[x];
            return cur_s;
        }
        int lvl = block[cur_s];
        if (s[x] < (1 << lvl)) {
            cur_s += upval[lvl][x];
            x = upnode[lvl][x]; continue;
        }
        if (s[x] <= cur_s) {
            cur_s += s[x];
            x = w[x]; continue;
        }
        for (int i = 23; i >= 0; i--) {
            if (cur_s < h[lvl][i][x]) {
                cur_s += g[lvl][i][x];
                x = f[lvl][i][x];
            }
            if (x == n + 1) return cur_s;
        }
    }
}

Compilation message (stderr)

dungeons.cpp: In function 'void predfs(int)':
dungeons.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < tree[node].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~
dungeons.cpp: In function 'void dfs(int, int, int)':
dungeons.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < tree[node].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~

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