Submission #1196164

#TimeUsernameProblemLanguageResultExecution timeMemory
1196164belgianbotDungeons Game (IOI21_dungeons)C++20
0 / 100
959 ms2162688 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 50001; const int LOG = 26; vector<long long> win(MAX_N); vector<vector<vector<long long>>> dist, nxt, mini; set<long long> temp; vector<int> s,p,w,l; int n; void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) { ios::sync_with_stdio(false); cin.tie(0); s = ss; p = pp; w = ww; l = ll; n = nn; l.push_back(n); p.push_back(0); s.push_back(0); w.push_back(n); for (int i = 0; i < n; i++) temp.insert(s[i]); dist.resize(MAX_N, vector<vector<long long>>(LOG, vector<long long>(temp.size()))); nxt.resize(MAX_N, vector<vector<long long>>(LOG, vector<long long>(temp.size()))); mini.resize(MAX_N, vector<vector<long long>>(LOG, vector<long long>(temp.size()))); auto it = temp.begin(); for (int i = 0; i < (int)(temp.size()); i++, it++){ for (int j = 0; j <= n; j++) { if (s[j] >= *it) { dist[j][0][i] = p[j]; nxt[j][0][i] = l[j]; mini[j][0][i] = s[l[j]]; }else { dist[j][0][i] = s[j]; nxt[j][0][i] = w[j]; mini[j][0][i] = *it; } } } for (int i = 0; i < (int)(temp.size()); i++){ for (int j = 0; j <= n; j++) { for (int k = 1; k < LOG; k++) { dist[j][k][i] = dist[j][k-1][i] + dist[nxt[j][k-1][i]][k-1][i]; nxt[j][k][i] = nxt[nxt[j][k-1][i]][k-1][i]; mini[j][k][i] = min(mini[j][k-1][i], mini[nxt[j][k-1][i]][k-1][i]); } } } win[n] = 0; for (int i = n-1; i >= 0; i--) { win[i] = win[w[i]] + s[i]; } return; } long long simulate(int x, int z) { long long st = z, pos = x; for (int i = 0; i < (int)(temp.size()); i++) { if (st >= (long long)(s[pos])) { st += s[pos]; pos = w[pos]; continue; } for (int j = LOG-1; j >= 0; j--) { if (st + dist[pos][j][i] >= mini[pos][j][i]) continue; st += dist[pos][j][i]; pos = nxt[pos][j][i]; } st += p[pos] + s[l[pos]]; pos = w[l[pos]]; } return st + win[pos]; }
#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...