Submission #625055

#TimeUsernameProblemLanguageResultExecution timeMemory
625055SuhaibSawalha1Dungeons Game (IOI21_dungeons)C++17
0 / 100
1 ms596 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; vector<int> s, p, w, l, dis; vector<vector<int>> anc; vector<vector<long long>> sum; int n; void dfs (int u) { if (u == n || dis[u]) { return; } dfs(w[u]); dis[u] = dis[w[u]] + 1; } void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) { ::n = n; ::s = s; ::p = p; ::w = w; ::l = l; dis.assign(n + 1, 0); anc.assign(20, vector<int>(n + 1, -1)); sum.assign(20, vector<long long>(n + 1, 0)); for (int i = 0; i < n; ++i) { dfs(i); anc[0][i] = l[i]; sum[0][i] = p[i]; } for (int i = 1; i < 20; ++i) { for (int j = 0; j <= n; ++j) { if (~anc[i - 1][j]) { anc[i][j] = anc[i - 1][anc[i - 1][j]]; sum[i][j] = sum[i - 1][j] + sum[i - 1][anc[i - 1][j]]; } } } return; } long long simulate(int x, int z) { long long ans = z; for (int i = 19; ~i && x < n; --i) { if (ans + sum[i][x] <= s[0]) { ans += sum[i][x]; x = anc[i][x]; } } return ans + (long long)dis[x] * s[0]; }
#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...