Submission #1042088

#TimeUsernameProblemLanguageResultExecution timeMemory
10420880npataDungeons Game (IOI21_dungeons)C++17
0 / 100
6 ms49496 KiB
#include "dungeons.h" #include<bits/stdc++.h> using namespace std; #define int long long #define vec vector const int MXN = 50'005; const int LOGN = 18; const int LOGS = 24; struct Data { int mnt; int sum; int v; }; Data binjmps[LOGS][MXN][LOGN]; int n; vec<int32_t> s; vec<int32_t> p; vec<int32_t> w; vec<int32_t> l; const int MXS = 1e7+5; void init(int32_t n_i, std::vector<int32_t> s_i, std::vector<int32_t> p_i, std::vector<int32_t> w_i, std::vector<int32_t> l_i) { // preprocessing fill in binjmps s = s_i; s.push_back(0); p = p_i; w = w_i; w.push_back(n_i); l = l_i; n = n_i; for(int i = 0; i<LOGS; i++) { for(int j = 0; j<=n; j++) { if(s[j] > (1<<i)) { binjmps[i][j][0] = {s[j], p[j], l[j]}; } else { binjmps[i][j][0] = {MXS, s[j], w[j]}; } } for(int k = 1; k<LOGN; k++) { for(int j = 0; j<=n; j++) { auto nxt = binjmps[i][binjmps[i][j][k-1].v][k-1]; auto me = binjmps[i][j][k-1]; int nxt_mnt = (nxt.mnt-me.sum > (1<<i)) ? nxt.mnt-me.sum : MXS; me = {min(me.mnt, nxt_mnt), me.sum+nxt.sum, nxt.v}; } } } return; } long long simulate(int32_t u, int32_t z) { int cur_s = z; for(int32_t i = 0; i<LOGS; i++) { for(int32_t j = LOGN-1; j>=0; j--) { if(binjmps[i][u][j].mnt > cur_s) { cur_s += binjmps[i][u][j].sum; u = binjmps[i][u][j].v; } } } return cur_s; }
#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...