# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1011107 | 1ne | Dungeons Game (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int k = 20;
vector<vector<long long>>table;
vector<vector<long long>>nx;
vector<vector<long long>>sum;
vector<long long>S,P,W,L;
long long N;
void init(long long n, std::vector<long long> s, std::vector<long long> p, std::vector<long long> w, std::vector<long long> l) {
table.resize(n,vector<long long>(k));
nx.resize(n,vector<long long>(k,-1));
sum.resize(n,vector<long long>(k,0));
N = n;
S = s;
P = p;
W = w;
L = l;
for (long long i = 0;i<n;++i){
table[i][0] = s[i];
nx[i][0] = w[i];
sum[i][0] = s[i];
}
for (long long i = 1;i<k;++i){
for (long long j = 0;j<n;++j){
if (nx[j][i - 1] == -1 || nx[j][i - 1] == n)continue;
//cout<<nx[j][i - 1]<<'\n';
nx[j][i] = nx[nx[j][i - 1]][i - 1];
table[j][i] = max(table[j][i - 1],table[nx[j][i - 1]][i - 1] - sum[j][i - 1]);
sum[j][i] = sum[j][i - 1] + sum[nx[j][i - 1]][i - 1];
}
}
return;
}
long long simulate(long long x, long long z) {
long long Z = z;
while(x != N){
// cout<<x<<"->";
long long c = 0;
while(nx[x][c] != -1 && table[x][c] <= Z){
++c;
}
if (c != 0){
Z+=sum[x][c - 1];
x = nx[x][c - 1];
}
if (x != N){
Z+=P[x];
x = L[x];
}
}
// cout<<'\n';
return Z;
}