| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1060842 | pcc | 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;
#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#define pll pair<ll,ll>
const int B = 25;
const int mxn = 5e4+10;
const int inf = 1e9;
int N;
int str[mxn],win[mxn],lose[mxn],cost[mxn];
struct JELLY{
int par[mxn][B];
ll sum[mxn][B];
ll mn[mxn][B];
JELLY(){
memset(par,-1,sizeof(par));
memset(sum,0,sizeof(sum));
}
void build(){
for(int i = 1;i<B;i++){
for(int j = 0;j<N;j++){
int pre = par[j][i-1];
if(pre == -1)continue;
par[j][i] = par[par[j][i-1]][i-1];
sum[j][i] = sum[j][i-1]+sum[pre][i-1];
sum[j][i] = min(sum[j][i],inf);
mn[j][i] = min(mn[pre][i-1],mn[j][i-1]+sum[pre][i-1]);
mn[j][i] = min(mn[j][i],inf);
}
}
return;
}
};
JELLY jel[B];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
for(int i = 0;i<N;i++){
str[i] = s[i];
cost[i] = p[i];
win[i] = w[i];
lose[i] = l[i];
}
win[N] = lose[N] = N;
for(int i = 0;i<N;i++){
int b = __lg(str[i])+1;
for(int j = 0;j<B;j++){
if(j>=b)jel[j].par[i][0] = win[i],jel[j].sum[i][0] = str[i],jel[j].mn[i][0] = inf;
else jel[j].par[i][0] = lose[i],jel[j].sum[i][0] = cost[i],jel[j].mn[i][0] = str[i];
}
}
for(auto &i:jel)i.build();
/*
cerr<<"JEL MN: "<<endl;for(int i = 0;i<N;i++){
for(int j = 0;j<B;j++)cerr<<jel[3].mn[i][j]<<' ';cerr<<endl;
}
cerr<<"JEL SUM: "<<endl;for(int i = 0;i<N;i++){
for(int j = 0;j<B;j++)cerr<<jel[3].sum[i][j]<<' ';cerr<<endl;
}
*/
return;
}
long long simulate(int x, int z) {
int now = x;
ll val = z;
for(int i = 0;i<B;i++){
//cerr<<"IN: "<<i<<":"<<now<<','<<val<<endl;
for(int j = B-1;j>=0;j--){
int pre = jel[i].par[now][j];
if(pre == -1)continue;
if(val+jel[i].sum[now][j]<jel[i].mn[now][j]){
val += jel[i].sum[now][j];
now = jel[i].par[now][j];
//cerr<<"JUMP: "<<i<<' '<<j<<' '<<now<<' '<<val<<endl;
}
}
if(now == N)break;
if(val>=str[now]){
val += str[now];
now = win[now];
}
else{
val += cost[now];
now = lose[now];
}
if(now == N)break;
}
assert(now == N);
return val;
}