제출 #443365

#제출 시각아이디문제언어결과실행 시간메모리
443365benedict0724던전 (IOI21_dungeons)C++17
13 / 100
159 ms41684 KiB
#include "dungeons.h" #include <vector> using namespace std; typedef long long ll; pair<int, ll> sp_lose[50002][25], sp_win[50002][25]; pair<int, ll> Plus(pair<int, ll> x, pair<int, ll> y) { pair<int, ll> ans; ans.first = y.first; ans.second = x.second + y.second; return ans; } int S; void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) { for(int i=0;i<n;i++) sp_lose[i][0] = {l[i], p[i]}; sp_lose[n][0] = {n, 0}; S = s[0]; for(int t=1;t<=24;t++) { for(int i=0;i<=n;i++) { int next = sp_lose[i][t-1].first; sp_lose[i][t] = Plus(sp_lose[i][t-1], sp_lose[next][t-1]); } } for(int i=0;i<n;i++) sp_win[i][0] = {w[i], s[i]}; sp_win[n][0] = {n, 0}; for(int t=1;t<=24;t++) { for(int i=0;i<=n;i++) { int next = sp_win[i][t-1].first; sp_win[i][t] = Plus(sp_win[i][t-1], sp_win[next][t-1]); } } return; } long long simulate(int x, int z) { if(z < S) { for(int t=24;t>=0;t--) { if(sp_lose[x][t].second + z < S) { z += sp_lose[x][t].second; x = sp_lose[x][t].first; } } z += sp_lose[x][0].second; x = sp_lose[x][0].first; } return z + sp_win[x][24].second; }
#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...