제출 #1042194

#제출 시각아이디문제언어결과실행 시간메모리
10421940npata던전 (IOI21_dungeons)C++17
26 / 100
541 ms311348 KiB
#include "dungeons.h" #include<bits/stdc++.h> using namespace std; #define int long long #define vec vector const int MXN = 400'050; const int LOGN = 30; const int LOGS = 30; struct Data { int mxt; int sum; int32_t v; }; Data binjmps[1][MXN][LOGN]; int n; vec<int32_t> s; vec<int32_t> p; vec<int32_t> w; vec<int32_t> l; const int MXS = 1e15+100; 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<1; i++) { for(int j = 0; j<=n; j++) { binjmps[i][j][0] = {s[j], 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->mxt-min(me->sum, (int)nxt->mxt)); binjmps[i][j][k] = {max(me->mxt, 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++) { //cerr << u << ' ' << cur_s << '\n'; for(int32_t j = LOGN-1; j>=0; j--) { if(binjmps[0][u][j].mxt <= cur_s) { cur_s += binjmps[0][u][j].sum; u = binjmps[0][u][j].v; } if(s[u] > cur_s) { cur_s += p[u]; u = l[u]; } } } assert(cur_s > 0); cerr << cur_s << '\n'; 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...