# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
437997 | Apiram | 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 <bits/stdc++.h>
using namespace std;
int nnn;
vector<int>sss,ppp,www,lll;
vector<long long >winning_path(400001,INT_MAX);
vector<int>adj[400001];
void gen(void);
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
nnn=nn;
sss=ss,ppp=pp,www=ww,lll=ll;
for(int i = 0 ; i < nnn ; i++) {
adj[www[i]].push_back(i);
}
gen();
}
void gen(void) {
vector<bool>vis(nnn+1,false);
winning_path.resize(nnn+1);
winning_path[nnn]=0;
queue<int>q;
q.push(nnn);
long long cnt=0;
while(!q.empty()) {
int sz = q.size();
while(sz--) {
int node = q.front();
q.pop();
vis[node]=true;
winning_path[node]=cnt;
for(auto z : adj[node]) {
if(!vis[z]) {
q.push(z);
}
}
}
cnt++;
}
}
long long simulate(int x, int zz) {
long long z=zz;
while(true) {
if(x==nnn) return z;
if(z >= sss[x] && winning_path[x]!=INT_MAX) {
long long mul = sss[x]*winning_path[x];
return z+mul;
}
z+=ppp[x];
x=lll[x];
}
}