제출 #442749

#제출 시각아이디문제언어결과실행 시간메모리
442749SorahISA던전 (IOI21_dungeons)C++17
63 / 100
2245 ms1285004 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 maxn = 5E4 + 5; const int lgmx = 24 + 1; const int INF = 1E13; int N; vector<int> S, P, W, L; vector<int> dep(maxn); int sum[lgmx][lgmx][maxn], anc[lgmx][lgmx][maxn], mnm[lgmx][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(sum, 0x00, sizeof(sum)); memset(mnm, 0x00, sizeof(mnm)); for (int i = N-1; i >= 0; --i) dep[i] = dep[W[i]] + S[i]; for (int lvl = 0; lvl < lgmx; ++lvl) { /** * Assume strength is in [2^{lvl}, 2^{lvl+1}), every opponent with strength * greater or equal to 2^{lvl+1} is ignored and you lose immediately as we * only consider opponents with strength less than 2^{lvl+1} in this level. **/ for (int i = 0; i <= N; ++i) { anc[lvl][0][i] = S[i] < (1<<(lvl+1)) ? W[i] : L[i]; sum[lvl][0][i] = S[i] < (1<<(lvl+1)) ? S[i] : P[i]; mnm[lvl][0][i] = S[i] < (1<<(lvl+1)) ? INF : S[i]; } for (int lay = 1; lay < lgmx; ++lay) { for (int i = 0; i <= N; ++i) { int par = anc[lvl][lay-1][i]; anc[lvl][lay][i] = anc[lvl][lay-1][par]; sum[lvl][lay][i] = sum[lvl][lay-1][i] + sum[lvl][lay-1][par]; int tmp = mnm[lvl][lay-1][par]; if (tmp != INF) tmp -= sum[lvl][lay-1][i]; mnm[lvl][lay][i] = min(mnm[lvl][lay-1][i], max((int)0, tmp)); } } } } int simulate(int32_t now, int32_t _Z) { int Z = _Z; for (int lvl = 0; lvl < lgmx; ++lvl) { for (int lay = lgmx-1; lay >= 0; --lay) { if (Z < mnm[lvl][lay][now]) { Z += sum[lvl][lay][now]; now = anc[lvl][lay][now]; } } // cerr << "lvl = " << lvl << ", Z = " << Z << ", now = " << now << "\n"; if (Z >= S[now]) Z += S[now], now = W[now]; else Z += P[now], now = L[now]; // cerr << "lvl = " << lvl << ", Z = " << Z << ", now = " << now << "\n"; } return Z + dep[now]; }
#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...