Submission #837381

#	Time	Username	Problem	Language	Result	Execution time	Memory
837381		FulopMate	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	117 ms	24888 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

int n;
vector<int> s, p, w, l;
long long S;
vector<int> windist;
vector<array<pair<long long, int>, 25>> par;

void calcwindist(int x){
    if(x == n)return;
    if(windist[x])return;
    calcwindist(w[x]);
    windist[x] = windist[w[x]]+1;
}

void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) {
	n = n_;
    s = s_, p = p_, w = w_, l = l_;
    S = s[0];

    windist.assign(n+1, 0);
    for(int i = 0; i < n; i++){
        calcwindist(i);
    }
    par.resize(n+1);
    for(int i = 0; i < 25; i++){
        par[n][i] = {0, n};
    }
    for(int i = 0; i < n; i++){
        par[i][0] = {p[i], l[i]};
    }
    for(int i = 1; i < 25; i++){
        for(int j = 0; j < n; j++){
            par[j][i] = {par[j][i-1].first + par[par[j][i-1].second][i-1].first,
                par[par[j][i-1].second][i-1].second};
        }
    }


    return;
}

long long simulate(int x, int z) {
    if(z >= S){
        return z + S*windist[x];
    }
    for(int i = 24; i >= 0; i--){
        if(x == n){
            return z;
        }
        if(par[x][i].first + z < S){
            z += par[x][i].first;
            x = par[x][i].second;
        }
    }
    if(x == n){
        return z;
    }
    z += par[x][0].first;
    x = par[x][0].second;
    return z + S * windist[x];
}

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