Submission #439953

#	Time	Username	Problem	Language	Result	Execution time	Memory
439953		dacin21	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	5705 ms	162560 KiB

dungeons

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") // codeforces

#undef _GLIBCXX_DEBUG

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

using ll = int64_t;

const int BLOCK = 1000;
const int MAX_SKILL = 1.01e7;
const int U = 20;
const int inf = 1e9;

int n;
struct Link{
    int to;
    int gain;
};
struct Node{
    Link win, loss;
    int thresh;
};
struct Jump{
    int to;
    int max_valid;
    ll gain;
};
vector<ll> win_gain;
vector<Node> g;
vector<vector<Jump> > jumps;

void init(int n_, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
	n = n_;
	g.assign(n+1, Node{});
	for(int i=0; i<n; ++i){
        g[i] = Node{Link{w[i], s[i]}, Link{l[i], p[i]}, s[i]};
	}
	g[n] = Node{Link{n, 0}, Link{n, 0}, 0};

	// compute win once we hit 1e7
	win_gain.assign(n+1, 0);
	for(int i=n-1; i>=0; --i){
        win_gain[i] = win_gain[g[i].win.to] + g[i].win.gain;
	}

	// assume we take BLOCK steps
	// then build jump table
	jumps.resize(U+1, vector<Jump>(n+1));
	for(int i=0; i<=n; ++i){
        if(g[i].thresh <= BLOCK){
            jumps[0][i] = Jump{g[i].win.to, inf, g[i].win.gain};
        } else {
            jumps[0][i] = Jump{g[i].loss.to, g[i].thresh-1, g[i].loss.gain};
        }
	}
	jumps[0][n].max_valid = 0;
	for(int i=1; i<=U; ++i){
	    for(int j=0; j<=n; ++j){
            auto &e = jumps[i-1][j];
            const int k = e.to;
            auto const&f = jumps[i-1][k];
            jumps[i][j] = Jump{f.to, max<ll>(-1, min<ll>(e.max_valid, f.max_valid-e.gain)), e.gain+f.gain};
	    }
	}
}

long long simulate(int x, int z) {
    int u = x;
    ll s = z;
    auto do_single_step = [&](){
        if(s >= g[u].thresh){
            s += g[u].win.gain;
            u = g[u].win.to;
        } else {
            s += g[u].loss.gain;
            u = g[u].loss.to;
        }
    };
    for(int it=0; it<BLOCK; ++it){
        do_single_step();
    }
    assert(u == n || s >= BLOCK);
    while(u != n && s < MAX_SKILL){
        int i = 0;
        while(i >= 0){
            auto &e = jumps[i][u];
            if(s < e.max_valid){
                s += e.gain;
                u = e.to;
                i = min(i+1, U);
            } else --i;
        }
        do_single_step();
    }
    s += win_gain[u];
    return s;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:65:45: warning: narrowing conversion of '(long int)std::max<long int>(-1, (* & std::min<long int>(((long int)e.Jump::max_valid), (((ll)((int)f.Jump::max_valid)) - e.Jump::gain))))' from 'long int' to 'int' [-Wnarrowing]
   65 |             jumps[i][j] = Jump{f.to, max<ll>(-1, min<ll>(e.max_valid, f.max_valid-e.gain)), e.gain+f.gain};
      |                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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