| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 579848 | joelau | 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;
long long N, S[400005], P[400005], W[400005], L[400005];
pair<long long,long long> lose[400005][25], win[400005][25];
void init(long long n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
N = n;
for (long long i = 0; i < N; ++i)
S[i] = s[i], P[i] = p[i], W[i] = w[i], L[i] = l[i], lose[i][0] = make_pair(L[i],P[i]), win[i][0] = make_pair(W[i],S[i]);
lose[N][0] = win[N][0] = make_pair(-1,-1);
for (long long k = 1; k < 25; ++k) for (long long i = 0; i <= N; ++i) {
if (lose[i][k-1] == make_pair(-1ll,-1ll)) lose[i][k] = make_pair(-1,-1);
else {
lose[i][k].first = lose[lose[i][k-1].first][k-1].first;
if (lose[i][k].first == -1) lose[i][k].second = -1;
else lose[i][k].second = lose[i][k-1].second + lose[lose[i][k-1].first][k-1].second;
}
if (win[i][k-1] == make_pair(-1ll,-1ll)) win[i][k] = make_pair(-1,-1);
else {
win[i][k].first = win[win[i][k-1].first][k-1].first;
if (win[i][k].first == -1) win[i][k].second = -1;
else win[i][k].second = win[i][k-1].second + win[win[i][k-1].first][k-1].second;
}
}
}
long long simulate(long long x, long long z) {
long long ans = z;
for (long long k = 24; k >= 0; --k)
if (lose[x][k] != make_pair(-1ll,-1ll) && ans+lose[x][k].second < S[0])
ans += lose[x][k].second, x = lose[x][k].first;
if (ans < S[0]) ans += lose[x][0].second, x = lose[x][0].first;
for (long long k = 24; k >= 0; --k)
if (win[x][k] != make_pair(-1ll,-1ll))
ans += win[x][k].second, x = win[x][k].first;
return ans;
}