제출 #592266

#제출 시각아이디문제언어결과실행 시간메모리
592266grt던전 (IOI21_dungeons)C++17
0 / 100
606 ms453880 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; int n; pair<int, ll>jp[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; 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]}; } else { jp[i][j][0] = {l[i], p[i]}; } } jp[n][j][0] = {n, 0}; } 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]; int num = (1 << j) + sum; int bit = 31 - __builtin_clz(num); jp[i][j][k] = {jp[id][bit][k - 1].ST, sum + jp[id][bit][k - 1].ND}; } jp[n][j][k] = {n, 0}; } } } 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 + jp[x][bit][i].ND < (1 << (bit + 1))) { z += jp[x][bit][i].ND; x = jp[x][bit][i].ST; } } 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...