제출 #592395

#제출 시각아이디문제언어결과실행 시간메모리
592395grt던전 (IOI21_dungeons)C++17
11 / 100
7119 ms751492 KiB
//GRT_2018 #include <bits/stdc++.h> #define PB push_back #define ST first #define ND second //mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); using namespace std; using ll = long long; using pi = pair<int,int>; using vi = vector<int>; const int nax = 50 * 1000 + 10, LOG = 24; const ll INF = 1e18; int n; pair<int, ll>jp[nax][LOG][16]; ll lim[nax][LOG][16]; vi s, p, w, l; void init(int N, vi _s, vi _p, vi _w, vi _l) { n = N; s = _s, w = _w, p = _p, l = _l; s.PB(n); for(int j = 0; j < LOG; ++j) { for(int i = 0; i < n; ++i) { int num = (1 << j); if(num >= s[i]) { jp[i][j][0] = {w[i], s[i]}; lim[i][j][0] = INF; } else { jp[i][j][0] = {l[i], p[i]}; lim[i][j][0] = s[i]; } } jp[n][j][0] = {n, 0}; lim[n][j][0] = INF; } for(int k = 1; k < 16; ++k) { for(int j = LOG - 1; j >= 0; --j) { for(int i = 0; i < n; ++i) { auto [id, sum] = jp[i][j][k - 1]; lim[i][j][k] = min(lim[i][j][k - 1], lim[id][j][k - 1] - sum); jp[i][j][k] = {jp[id][j][k - 1].ST, sum + jp[id][j][k - 1].ND}; } jp[n][j][k] = {n, 0}; lim[n][j][k] = INF; } } } ll simulate(int x, int zz) { int inf = 10'000'000; ll z = zz; while(x != n) { int bit = LOG - 1; if(z < inf) { bit = 31 - __builtin_clz(z); } for(int i = 15; i >= 0; --i) { if(z < lim[x][bit][i]) { z += jp[x][bit][i].ND; x = jp[x][bit][i].ST; } } // cerr << x << " " << z << "\n"; if(x == n) { return z; } if(z >= s[x]) { z += s[x]; x = w[x]; } else { 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...