Submission #1072195

#TimeUsernameProblemLanguageResultExecution timeMemory
1072195TAhmed33Dungeons Game (IOI21_dungeons)C++17
0 / 100
100 ms52632 KiB
#include "dungeons.h" #include <bits/stdc++.h> #pragma GCC optimize ("trapv") using namespace std; typedef long long ll; const int MAXN = 4e5 + 25; const ll inf = 1e9; const int B = 60; ll n, s[MAXN], p[MAXN], w[MAXN], l[MAXN], dp[MAXN]; ll ss[B][MAXN], tt[B][MAXN]; void init (int N, vector <int> S, vector <int> P, vector <int> W, vector <int> L) { n = N; for (int i = 0; i < n; i++) { s[i] = S[i]; p[i] = P[i]; w[i] = W[i]; l[i] = L[i]; } for (int i = n - 1; i >= 0; i--) { dp[i] = s[i] + dp[w[i]]; } for (int i = 0; i < n; i++) { ss[0][i] = l[i]; tt[0][i] = p[i]; tt[0][i] = min(tt[0][i], inf); } for (int i = 1; i < B; i++) { for (int j = 0; j < n; j++) { ss[i][j] = ss[i - 1][ss[i - 1][j]]; tt[i][j] = tt[i - 1][j] + tt[i - 1][ss[i - 1][j]]; tt[i][j] = min(tt[i][j], inf); } } } ll simulate (int x, int z) { if (z >= s[0]) { return z + dp[x]; } int pos = x; ll sum = z; for (int i = B - 1; i >= 0; i--) { if (sum + tt[i][pos] < s[0]) { sum += tt[i][pos]; pos = ss[i][pos]; } } sum += tt[0][pos]; pos = ss[0][pos]; return sum + dp[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...