Submission #1195991

#TimeUsernameProblemLanguageResultExecution timeMemory
1195991belgianbotDungeons Game (IOI21_dungeons)C++20
13 / 100
86 ms26500 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<pair<long long, int>>> vec(MAX_N, vector<pair<long long,int>>(LOG)); vector<int> s,p,w,l, toCycle(MAX_N); 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); for (int i = 0; i <= n; i++) { vec[i][0] = {(long long)(p[i]), l[i]}; } for (int i = 1; i < LOG; i++) { for (int j = 0; j <= n; j++) { vec[j][i] = {vec[vec[j][i-1].second][i-1].first + vec[j][i-1].first, vec[vec[j][i-1].second][i-1].second}; } } 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 lim = s[x]; long long st = z; int pos = x; if (st >= lim) return st+ win[pos]; for (int i = LOG-1; i >= 0; i--) { if (st + vec[pos][i].first >= lim) continue; st += vec[pos][i].first; pos = vec[pos][i].second; } return st + p[pos] + win[l[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...