Submission #1210432

#TimeUsernameProblemLanguageResultExecution timeMemory
1210432steveonalexDungeons Game (IOI21_dungeons)C++20
100 / 100
2095 ms448500 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define MASK(i) (1ULL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) #define ALL(v) (v).begin(), (v).end() ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll gcd(ll a, ll b){return __gcd(a, b);} ll lcm(ll a, ll b){return a / gcd(a, b) * b;} ll LASTBIT(ll mask){return (mask) & (-mask);} int pop_cnt(ull mask){return __builtin_popcountll(mask);} int ctz(ull mask){return __builtin_ctzll(mask);} int logOf(ull mask){return 63 - __builtin_clzll(mask);} mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);} double rngesus_d(double l, double r){ double wow = (double) ((ull) rng()) / ((ull)(0-1)); return wow * (r - l) + l; } template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b) {a = b; return true;} return false; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b) {a = b; return true;} return false; } template <class T> void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){ for(auto item: container) out << item << separator; out << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } #include "dungeons.h" const int N = 4e5 + 69; const int LOG_A = 25; const ll INF = 1e18 + 69; int n; int s[N], p[N], w[N], l[N]; int nxt[LOG_A][N], jump_length[LOG_A][N]; bool cycle_root[LOG_A][N]; ll cost[LOG_A][N], barber[LOG_A][N]; ll threshold[LOG_A][N]; int gain[LOG_A][N], graph[LOG_A][N]; pair<ll, ll> cycle_cost[LOG_A][N]; int visited[N]; int get_layer(ll z){ if (z == 0) return 0; return min(logOf(z), LOG_A - 1); } void go(int layer, int u){ if (visited[u] == 2) return; if (visited[u] == 1){ pair<ll, ll> cur_cost = make_pair(0, INF); int v = u; while(visited[v] == 1){ visited[v] = 2; cur_cost = make_pair(cur_cost.first + gain[layer][v], min(cur_cost.second, threshold[layer][v] - cur_cost.first)); v = graph[layer][v]; } cycle_root[layer][u] = true; cycle_cost[layer][u] = cur_cost; jump_length[layer][u] = 0; nxt[layer][u] = u; return; } visited[u] = 1; int v = graph[layer][u]; go(layer, v); if (cycle_root[layer][u]) return; int v1 = nxt[layer][v]; if (jump_length[layer][v] == 0 || jump_length[layer][v] != jump_length[layer][v1]){ nxt[layer][u] = v; jump_length[layer][u] = 1; cost[layer][u] = gain[layer][u]; barber[layer][u] = threshold[layer][u]; } else{ int v1 = nxt[layer][v], v2 = nxt[layer][v1]; nxt[layer][u] = v2; jump_length[layer][u] = jump_length[layer][v] * 2 + 1; cost[layer][u] = gain[layer][u] + cost[layer][v] + cost[layer][v1]; barber[layer][u] = min({threshold[layer][u], barber[layer][v] - gain[layer][u], barber[layer][v1] - gain[layer][u] - cost[layer][v]}); } visited[u] = 2; } void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l){ n = _n; if (n >= N) assert(false); for(int i= 0; i < n; ++i) { s[i] = _s[i]; p[i] = _p[i]; w[i] = _w[i]; l[i] = _l[i]; } w[n] = l[n] = n; s[n] = p[n] = 0; for(int layer = 0; layer < LOG_A; ++layer){ vector<ll> s1(n+1), p1(n+1), w1(n+1); for(int i = 0; i <= n; ++i){ int cur = get_layer(s[i]); if (cur < layer){ threshold[layer][i] = INF; gain[layer][i] = s[i]; graph[layer][i] = w[i]; } else if (cur > layer){ threshold[layer][i] = INF; gain[layer][i] = p[i]; graph[layer][i] = l[i]; } else{ threshold[layer][i] = s[i]; gain[layer][i] = p[i]; graph[layer][i] = l[i]; } } for(int i = 0; i <= n; ++i) visited[i] = 0; for(int i = 0; i <= n; ++i) if (visited[i] == 0){ go(layer, i); } } } ll simulate(int x, int z){ ll ans = z; while(true){ if (x == n) break; int layer = get_layer(ans); while(true){ if (cycle_root[layer][x]){ ll bound = MASK(layer + 1) - 1; if (layer == LOG_A) bound = INF; minimize(bound, cycle_cost[layer][x].second + cycle_cost[layer][x].first - 1); if (bound >= ans){ ans += (bound - ans) - (bound - ans) % cycle_cost[layer][x].first; } } if (jump_length[layer][x] != 0 && nxt[layer][x] != n && get_layer(ans + cost[layer][x]) == layer && ans < barber[layer][x]){ ans += cost[layer][x]; x = nxt[layer][x]; } else if (graph[layer][x] != n && get_layer(ans + gain[layer][x]) == layer && ans < threshold[layer][x]){ ans += gain[layer][x]; x = graph[layer][x]; } else break; } if (ans >= s[x]){ ans += s[x]; x = w[x]; } else{ ans += p[x]; x = l[x]; } if (x == n) break; } return ans; }
#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...