Submission #1049169

#TimeUsernameProblemLanguageResultExecution timeMemory
1049169Alihan_8Dungeons Game (IOI21_dungeons)C++17
37 / 100
7027 ms352624 KiB
#include "dungeons.h" #include <vector> #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define ar array #define pb push_back #define ln '\n' //#define int long long using i64 = long long; template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } const i64 inf = 1e15; const int L = 30; vector <int> s, p, w, l; vector <vector<i64>> need, S, U; int n; void init(int n_, std::vector<int> s_, std::vector<int> p_, std::vector<int> w_, std::vector<int> l_) { n = n_, s = s_, p = p_, w = w_, l = l_; need.resize(n + 1); S.resize(n + 1); U.resize(n + 1); for ( int i = 0; i <= n; i++ ){ need[i].resize(L); S[i].resize(L); U[i].resize(L); if ( i == n ) continue; need[i][0] = s[i]; S[i][0] = s[i]; U[i][0] = w[i]; } U[n][0] = n; for ( int i = 1; i < L; i++ ){ for ( int j = 0; j <= n; j++ ){ U[j][i] = U[U[j][i - 1]][i - 1]; S[j][i] = min(inf, S[j][i - 1] + S[U[j][i - 1]][i - 1]); need[j][i] = max(need[j][i - 1], need[U[j][i - 1]][i - 1] - S[j][i - 1]); } } } long long simulate(int x, int Z) { // subtask #2 i64 z = Z; while ( x < n ){ for ( int i = L - 1; i >= 0; i-- ){ if ( U[x][i] != n && need[x][i] <= z ){ z += S[x][i]; x = U[x][i]; } } if ( s[x] <= z ){ z += s[x]; x = w[x]; continue; } if ( x == n ) break; z += p[x]; x = l[x]; } return z; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...