| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1195945 | belgianbot | Dungeons Game (IOI21_dungeons) | C++20 | 0 ms | 0 KiB |
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50001;
vector<bool> processed(MAX_N,false), is_processing(MAX_N, false), is_cycle(MAX_N, false);
vector<long long> cycle(MAX_N), win(MAX_N), distCycle(MAX_N);
vector<int> s,p,w,l, toCycle(MAX_N);
stack<int> q;
int n;
int proc(int i) {
if (i == n) return;
if (is_processing[i]) {
while(!q.empty()) {
int x = q.top(); q.pop();
is_processing[x] = false;
is_cycle[x] = true;
distCycle[x] = 0;
if (x == i) break;
}
return i;
}
if (processed[i]) return toCycle[i];
is_processing[i] = true;
processed[i] =true;
q.push(i);
proc(l[i]);
}
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
ios::sync_with_stdio(false);
cin.tie(0);
s = ss; p = pp; w = ww; l = ll; n = nn;
for (int i = 0; i < n; i++) {
if (!processed[i]) {
int cy = proc(i);
long long sz = distCycle[cy];
while (!q.empty()) {
int x = q.top(); q.pop();
sz += p[x];
distCycle[x] = sz;
toCycle[x] = cy;
is_processing[x] = false;
}
}
}
processed.clear();
processed.resize(MAX_N,false);
for (int i = 0; i < n; i++) {
if (processed[i] || !is_cycle[i]) continue;
int pos = i;
long long sz = 0;
while (!processed[pos]) {
processed[pos] = true;
q.push(pos);
sz += p[pos];
pos = l[pos];
}
while (!q.empty()) {
int x = q.top(); q.pop();
cycle[x] = sz;
}
}
win[n] = 0;
for (int i = n-1; i >= 0; i--) {
win[i] = win[w[i]] + s[i];
}
return;
}
long long simulate(int x, int z) {
long long lim = s[x];
long long st = z;
int pos = x;
if (st >= lim) return st+ win[pos];
if (st + distCycle[pos] < lim) {
while (!is_cycle[pos] && st < lim && pos != n) {
st += (long long)(p[pos]);
pos = l[pos];
}
if (pos == n) return st;
if (st >= lim) return st + win[pos];
}
st += distCycle[pos];
pos = toCycle[pos];
st += ((lim - st) / cycle[pos]) * cycle[pos];
while (st < lim && pos != n) {
st += (long long)(p[pos]);
pos = l[pos];
}
if (pos == n) return st;
return st + win[pos];
}