Submission #804656

#TimeUsernameProblemLanguageResultExecution timeMemory
804656SamAndDungeons Game (IOI21_dungeons)C++17
0 / 100
8 ms11252 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define m_p make_pair #define sz(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() typedef long long ll; const int N = 400005; const int m = 28; int n; vector<int> S, P, W, L; vector<int> t[N]; ll st[m][N]; int ut[m][N]; void dfst(int x, int j) { if (x == n || S[x] >= (1 << j)) { st[j][x] = 0; ut[j][x] = x; } for (int i = 0; i < sz(t[x]); ++i) { int h = t[x][i]; ut[j][h] = ut[j][x]; st[j][h] = st[j][x] + S[h]; dfst(h, j); } } pair<int, ll> u[m][N]; void init(int NN, std::vector<int> SS, std::vector<int> PP, std::vector<int> WW, std::vector<int> LL) { n = NN; S = SS; P = PP; W = WW; L = LL; for (int i = 0; i < n; ++i) { t[W[i]].push_back(i); } for (int j = 0; j < m; ++j) { dfst(n, j); for (int x = 0; x < n; ++x) { if (S[x] >= (1 << j)) { u[j][x] = m_p(ut[j][L[x]], P[x] + st[j][L[x]]); } } u[j][n] = m_p(n, 0); } } long long simulate(int x, int Z) { ll z = Z; while (x != n) { for (int j = 0; j < m; ++j) { if (z < (1 << j)) { z += st[j][x]; x = ut[j][x]; while (x != n && z < S[x]) { z += u[j][x].se; x = u[j][x].fi; } break; } } } return 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...