| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 604229 | 2fat2code | 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>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;
const int nmax = 400005;
// baza 7
int N;
pair<pair<long long, long long>,int>lca[nmax][10][25];
vector<int>S, W;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
for(auto &it : w) ++it;
for(auto &it : l) ++it;
S = s; W = w;
N = n;
for(int j=0;j<=24;j++){
for(int i=1;i<=n;i++){
if(s[i - 1] < (1 << j)){
lca[i][0][j].sc = w[i - 1];
lca[i][0][j].fr.fr = s[i - 1];
lca[i][0][j].fr.sc = -1e18;
}
else{
lca[i][0][j].sc = l[i - 1];
lca[i][0][j].fr.fr = p[i - 1];
lca[i][0][j].fr.sc = -s[i - 1];
}
}
}
for(int k=1;k<=9;k++){
for(int j=0;j<=24;j++){
for(int i=1;i<=n;i++){
int slavic = lca[i][k-1][j].sc;
lca[i][k][j].fr.fr = lca[i][k-1][j].fr.fr;
lca[i][k][j].fr.sc = lca[i][k-1][j].fr.sc;
for(int lol=1;lol<=6;lol++){
lca[i][k][j].fr.sc = max(lca[i][k][j].fr.sc, lca[i][k][j].fr.fr + lca[slavic][k-1][j].fr.sc);
lca[i][k][j].fr.fr += lca[slavic][k-1][j].fr.fr;
slavic = lca[slavic][k-1][j].sc;
}
lca[i][k][j].sc = slavic;
}
}
}
}
long long simulate(int x, int z) {
int pos_curr = x + 1;
long long putere_curr = z;
int i = 0;
while(pos_curr != N + 1){
for(int j=9;j>=0;j--){
for(int pizdet=1;pizdet<=6;pizdet++){
if(lca[pos_curr][j][i].sc != 0 && lca[pos_curr][j][i].fr.sc + putere_curr < 0LL){
putere_curr += lca[pos_curr][j][i].fr.fr;
pos_curr = lca[pos_curr][j][i].sc;
}
}
}
if(pos_curr == N + 1) break;
else{
putere_curr += (long long)S[pos_curr - 1];
pos_curr = W[pos_curr - 1];
++i;
}
}
return putere_curr;
}