제출 #626392

#제출 시각아이디문제언어결과실행 시간메모리
626392juancarlovieri던전 (IOI21_dungeons)C++17
0 / 100
2 ms980 KiB
#include "dungeons.h" #include <vector> #include <bits/stdc++.h> using namespace std; int n; vector<int> s, p, w, l; pair<int, pair<int, int>> win[400005][25]; pair<int, pair<int, int>> los[400005][25]; void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) { n = N, s = S, p = P, w = W, l = L; for (int i = 0; i < n; ++i) { win[i][0] = {s[i], {s[i], w[i]}}; los[i][0] = {s[i] - 1, {p[i], l[i]}}; } for (int j = 1; j < 24; ++j) { for (int i = 0; i < n; ++i) { if (win[i][j - 1].second.second == n) { win[i][j] = win[i][j - 1]; } else { auto lft = win[i][j - 1]; auto rgt = win[win[i][j - 1].second.second][j - 1]; int aft = lft.first + lft.second.first; win[i][j] = {lft.first + max(0ll, 1ll * rgt.first - aft), {lft.second.first + rgt.second.first, rgt.second.second}}; } if (los[i][j - 1].second.second == n) { los[i][j] = los[i][j - 1]; } else { auto lft = los[i][j - 1]; auto rgt = los[lft.second.second][j - 1]; int aft = lft.first + lft.second.first; los[i][j] = {lft.first - max(0ll, 1ll * aft - rgt.first), {lft.second.first + rgt.second.first, rgt.second.second}}; } } } return; } long long simulate(int x, int z) { // int ans = 0; while (x != n) { for (int i = 23; i >= 0; --i) { if (x == n) break; if (win[x][i].first <= z) { auto cur = win[x][i]; x = cur.second.second; z += cur.second.first; } } for (int i = 23; i >= 0; --i) { if (x == n) break; if (los[x][i].first >= z) { auto cur = los[x][i]; x = cur.second.second; z += cur.second.first; } } } 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...