Submission #442849

#TimeUsernameProblemLanguageResultExecution timeMemory
442849baluteshihDungeons Game (IOI21_dungeons)C++17
37 / 100
7075 ms172884 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define X first #define Y second #define ALL(v) v.begin(), v.end() #define pb push_back #define SZ(a) ((int)a.size()) struct node { int to, lower; ll sum; node operator+(const node &a) const { node rt; rt.to = a.to; rt.sum = sum + a.sum; if (lower + sum < a.lower) rt.lower = a.lower - sum; else rt.lower = lower; return rt; } }; int N, lg = __lg(10000000); vector<int> S, P, W, L; vector<node> dp[30]; 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; dp[0].resize(N + 1); dp[0][N] = node{N, 0, 0}; for (int i = 0; i < N; ++i) dp[0][i] = node{W[i], S[i], S[i]}; for (int i = 1; i <= lg; ++i) { dp[i].resize(N + 1); for (int j = 0; j <= N; ++j) dp[i][j] = dp[i - 1][j] + dp[i - 1][dp[i - 1][j].to]; } } long long simulate(int x, int z) { ll nw = z; while (dp[lg][x].lower > nw) { for (int i = lg; i >= 0; --i) if (dp[i][x].lower <= nw) { nw += dp[i][x].sum; x = dp[i][x].to; } nw += P[x]; x = L[x]; } return nw + dp[lg][x].sum; }
#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...