| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1243386 | guanex | Dungeons Game (IOI21_dungeons) | C++20 | 0 ms | 0 KiB |
#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N;
ll win[100005][30];//endpoint of win streak
ll stopwin[100005][30];//max on the range
ll winsum[100005][30];//sum of the win streak
ll lose[100005][30]; // endpoint of lose streak
ll stoplose[100005][30]; // min on the range
ll losesum[100005][30]; // sum of teh lose streak
ll v[100005];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
for(ll i = 0; i < n; ++i){
v[i] = s[i];
winsum[i][0] = s[i];
losesum[i][0] = p[i];
if(i == 1073){
//cout << s[i] << " " << p[i] << " " << w[i] << " " << l[i] << endl;
}
win[i][0] = w[i];
lose[i][0] = l[i];
if(w[i] == n){
stopwin[i][0] = 1e16;
}else
stopwin[i][0] = max(s[i] + s[i], s[w[i]]);
if(l[i] == n){
stoplose[i][0] = -1;
}else
stoplose[i][0] = min(s[i] + p[i], s[l[i]]);
}
win[n][0] = n;
lose[n][0] = n;
winsum[n][0] = 0;
losesum[n][0] = 0;
stopwin[n][0] = 1e16;
stoplose[n][0] = -1;
for(ll j = 1; j < 30; ++j){
for(ll i = 0; i < n; ++i){
win[i][j] = win[win[i][j-1]][j-1];
lose[i][j] = lose[lose[i][j-1]][j-1];
winsum[i][j] = winsum[i][j-1] + winsum[win[i][j-1]][j-1];
if(winsum[i][j] > 10000000000000000){
winsum[i][j] = 10000000000000000;
}
losesum[i][j] = losesum[i][j-1] + losesum[lose[i][j-1]][j-1];
if(losesum[i][j] > 10000000000000000){
losesum[i][j] = 10000000000000000;
}
stopwin[i][j] = max(stopwin[i][j-1] + winsum[win[i][j-1]][j-1], stopwin[win[i][j-1]][j-1]);
stoplose[i][j] = min(stoplose[i][j-1] + losesum[lose[i][j-1]][j-1], stoplose[lose[i][j-1]][j-1]);
}
}
return;
}
ll checkwin(ll no, ll &s){
for(ll i = 29; i >= 0; --i){
ll ns = s + winsum[no][i];
if(stopwin[no][i] > ns){
continue;
}
//cout << stopwin[no][i] << " ";
s += winsum[no][i];
no = win[no][i];
//cout << no << " " << s<< endl;
}
s += winsum[no][0];
return win[no][0];
}
ll checklose(ll no, ll &s){
//cout << no << " " << s << endl;
for(ll i = 29; i >= 0; --i){
ll ns = s + losesum[no][i];
//cout << stoplose[no][i] << " " << no << " " << ns << " " << i << endl;
if(stoplose[no][i] <= ns){
continue;
}
//cout << stoplose[no][i] << " ";
s += losesum[no][i];
no = lose[no][i];
//cout << no << " " << s << endl;
}
s += losesum[no][0];
//cout << lose[no][0] << " " << s << endl;
return lose[no][0];
}
long long simulate(int x, int z) {
//cout << stoplose[0][0] << " " << stoplose[1][1] << endl;
ll no = x;
ll s = z;
ll parity = 0; //0 -> starts losing 1 -> starts winning
if(x == n){
return z;
}
if(z >= v[x]){
parity = 1;
}
while(no != N){
//cout << no << endl;
// i get my new endpoint after the win/lose streak
//cout << parity << " " << no << " " << s << " im trying bro" << endl;
if(parity == 1){
no = checkwin(no, s);
parity = 0;
}else{
no = checklose(no, s);
parity = 1;
}
//cout << no << " " << s << endl;
}
return s;
}