Submission #604527

#	Time	Username	Problem	Language	Result	Execution time	Memory
604527		2fat2code	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	6736 ms	2056848 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 400005;

// baza 10

int N, putere[9];
pair<pair<long long, long long>,int>lca[nmax][24][9];
vector<int>S, W;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    putere[0] = 1;
    for(int i=1;i<=8;i++) putere[i] = putere[i-1] * 8;
    for(auto &it : w) ++it;
    for(auto &it : l) ++it;
    S = s; W = w;
    N = n;
    for(int j=0;j<=8;j++){
        for(int i=1;i<=n;i++){
            if(s[i - 1] < putere[j]){
                lca[i][0][j].sc = w[i - 1];
                lca[i][0][j].fr.fr = s[i - 1];
                lca[i][0][j].fr.sc = -1e18;
            }
            else{
                lca[i][0][j].sc = l[i - 1];
                lca[i][0][j].fr.fr = p[i - 1];
                lca[i][0][j].fr.sc = -s[i - 1];
            }
        }
    }
    for(int k=1;k<=23;k++){
        for(int j=0;j<=8;j++){
            for(int i=1;i<=n;i++){
                lca[i][k][j].sc = lca[lca[i][k-1][j].sc][k-1][j].sc;
                lca[i][k][j].fr.fr = lca[i][k-1][j].fr.fr + lca[lca[i][k-1][j].sc][k-1][j].fr.fr;
                lca[i][k][j].fr.sc = max(lca[i][k-1][j].fr.sc, lca[i][k-1][j].fr.fr + lca[lca[i][k-1][j].sc][k-1][j].fr.sc);
            }
        }
    }
}

long long simulate(int x, int z) {
    int pos_curr = x + 1;
    long long putere_curr = z;
    int i = 0;
    int t = 0;
    while(pos_curr != N + 1){
        if(t == 7){
            i++;
            t = 0;
        }
        for(int j=23;j>=0;j--){
            if(lca[pos_curr][j][i].sc && lca[pos_curr][j][i].fr.sc + putere_curr < 0LL){
                putere_curr += lca[pos_curr][j][i].fr.fr;
                pos_curr = lca[pos_curr][j][i].sc;
            }
        }
        if(pos_curr == N + 1) break;
        else{
            ++t;
            putere_curr += (long long)S[pos_curr - 1];
            pos_curr = W[pos_curr - 1];
        }
    }
    return putere_curr;
}

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