Submission #1048903

#TimeUsernameProblemLanguageResultExecution timeMemory
1048903AmirAli_H1Dungeons Game (IOI21_dungeons)C++17
37 / 100
255 ms244816 KiB
// In the name of Allah #include <bits/stdc++.h> #include "dungeons.h" using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define endl '\n' #define sep ' ' #define F first #define S second #define all(x) (x).begin(),(x).end() #define len(x) ((ll) (x).size()) #define pb push_back #define Mp make_pair int n, q; bool ok = 1; const int maxn = 4e5 + 7; const int maxlg = 20, maxlgx = 25; const ll oo = 1e18 + 4; ll val1[maxn], val2[maxn], A1[maxn], A2[maxn]; ll sm[maxn], valx[maxn]; ll mx[maxn][maxlg]; int up[maxn][maxlg]; ll Ax[maxn][maxlgx]; int upx[maxn][maxlgx]; void init(int Nx, vector<int> s, vector<int> p, vector<int> w, vector<int> l) { n = Nx; for (int i = 0; i < n; i++) { A1[i] = w[i]; A2[i] = l[i]; val1[i] = s[i]; val2[i] = p[i]; if (val1[i] != val1[0]) ok = 0; } A1[n] = n; val1[n] = 0; sm[n] = 0; valx[n] = 0; for (int i = n - 1; i >= 0; i--) { int j = A1[i]; sm[i] = sm[j] + val1[i]; valx[i] = val1[i] + sm[i]; } for (int i = n; i >= 0; i--) { up[i][0] = A1[i]; mx[i][0] = valx[i]; for (int j = 1; j < maxlg; j++) { int r = up[i][j - 1]; up[i][j] = up[r][j - 1]; mx[i][j] = max(mx[i][j - 1], mx[r][j - 1]); } } for (int j = 0; j < maxlgx; j++) { for (int i = 0; i < n; i++) { if (j == 0) { upx[i][j] = A2[i]; Ax[i][j] = val2[i]; } else { int r = upx[i][j - 1]; upx[i][j] = upx[r][j - 1]; Ax[i][j] = min(oo, Ax[i][j - 1] + Ax[r][j - 1]); } } } } ll cal(int i, ll x) { if (i == n) return x; if (x < val1[i]) return cal(A2[i], x + val2[i]); ll R = x + sm[i]; for (int j = maxlg - 1; j >= 0; j--) { if (mx[i][j] <= R) { x += sm[i]; x -= sm[up[i][j]]; i = up[i][j]; } } return cal(i, x); } ll calx(int i, ll x) { if (i == n) return x; if (x >= val1[i]) return x + sm[i]; for (int j = maxlgx - 1; j >= 0; j--) { if (x + Ax[i][j] < val1[i]) { x += Ax[i][j]; i = upx[i][j]; } } x += Ax[i][0]; i = upx[i][0]; return x + sm[i]; } ll simulate(int x, int z) { if (!ok) return cal(x, z); else return calx(x, z); }
#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...