Submission #442814

#TimeUsernameProblemLanguageResultExecution timeMemory
442814SorahISADungeons Game (IOI21_dungeons)C++17
37 / 100
472 ms204836 KiB
#include "dungeons.h" #pragma GCC optimize("Ofast", "unroll-loops") #include <bits/stdc++.h> using namespace std; #define int long long // #define double long double using pii = pair<int, int>; template<typename T> using Prior = std::priority_queue<T>; template<typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>; #define X first #define Y second #define eb emplace_back #define pb pop_back #define pf pop_front #define ALL(x) begin(x), end(x) #define RALL(x) rbegin(x), rend(x) namespace { mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 4E5 + 5; const int lgmx = 19; int N; vector<int> S, P, W, L; int anc[lgmx][maxn], mxm[lgmx][maxn], sum[lgmx][maxn]; } /// end of namespace void init(int32_t _N, vector<int32_t> _S, vector<int32_t> _P, vector<int32_t> _W, vector<int32_t> _L) { N = _N; for (auto &x : _S) S.eb(x); for (auto &x : _P) P.eb(x); for (auto &x : _W) W.eb(x); for (auto &x : _L) L.eb(x); S.eb(0), P.eb(0), W.eb(N), L.eb(N); memset(anc, 0x00, sizeof(anc)); memset(mxm, 0x00, sizeof(mxm)); memset(sum, 0x00, sizeof(sum)); for (int i = 0; i <= N; ++i) { anc[0][i] = W[i]; mxm[0][i] = S[i]; sum[0][i] = S[i]; } for (int lay = 1; lay < lgmx; ++lay) { for (int i = 0; i <= N; ++i) { int par = anc[lay-1][i]; anc[lay][i] = anc[lay-1][par]; mxm[lay][i] = max(mxm[lay-1][i], mxm[lay-1][par]); sum[lay][i] = sum[lay-1][i] + sum[lay-1][par]; } } } int simulate(int32_t now, int32_t Z) { /// s[i] = p[i] /// while (now != N) { // cerr << "now: " << now << " " << Z << "\n"; for (int lay = lgmx-1; lay >= 0; --lay) { // cerr << lay << " " << now << " " << mxm[lay][now] << "\n"; if (Z >= mxm[lay][now]) { Z += sum[lay][now]; now = anc[lay][now]; } } if (Z >= S[now]) Z += S[now], now = W[now]; else Z += P[now], now = L[now]; } 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...