Submission #1211496

#TimeUsernameProblemLanguageResultExecution timeMemory
1211496ksu2009enDungeons Game (IOI21_dungeons)C++20
0 / 100
59 ms36680 KiB
#include <iostream> #include <vector> #include <string> #include <math.h> #include <cmath> #include <iomanip> #include <cstdio> #include <algorithm> #include <numeric> #include <map> #include <set> #include <queue> #include <stack> #include <deque> #include <bitset> #include <cstring> #include <unordered_map> using namespace std; typedef long long ll; #include "dungeons.h" vector<ll> s, p, w, l; ll n; ll win[(ll)(5e4 + 7)], comp[(ll)(5e4 + 7)]; vector<ll> d[(ll)(5e4 + 7)], d2[(ll)(5e4 + 7)]; void find_comp(ll v, ll step){ comp[v] = step; for(auto i: d[v]){ if(!comp[i]) find_comp(i, step); } } vector<ll> ord; ll used[(ll)(5e4 + 7)], par[(ll)(5e4 + 7)], tot[(ll)(5e4 + 7)]; pair<ll, ll> t[(ll)(5e4 + 7)][22]; bool loop[(ll)(5e4 + 7)]; void find_loop(ll v, ll prev){ used[v] = 1; par[v] = prev; for(auto i: d2[v]){ if(used[i] == 1){ ll cur = v; while(cur != -1 && cur != i){ ord.push_back(cur); cur = par[cur]; } ord.push_back(i); } else if(!used[i]){ find_loop(i, v); } } used[v] = 2; } ll par_pos[(ll)(5e4 + 7)]; vector<ll> pref[(ll)(5e4 + 7)]; vector<ll> loops[(ll)(5e4 + 7)]; void build(ll v, ll par){ t[v][0].first = par; if(par != 0) t[v][0].second = p[v]; for(ll i = 1; i < 20; i++){ t[v][i].first = t[t[v][i - 1].first][i - 1].first; t[v][i].second = t[v][i - 1].second + t[t[v][i - 1].first][i - 1].second; } for(auto i: d[v]){ if(i != par && !loop[i]) build(i, v); } } void init(int n0, std::vector<int> s0, std::vector<int> p0, std::vector<int> w0, std::vector<int> l0){ n = n0; s.clear(); p.clear(); w.clear(); l.clear(); for(int i = 0; i <= n; i++){ pref[i].clear(); loops[i].clear(); d[i].clear(); d2[i].clear(); for(int j = 0; j < 20; j++) t[i][j].first = t[i][j].second = 0; par_pos[i] = used[i] = par[i] = tot[i] = loop[i] = win[i] = comp[i] = 0; } s.resize(n + 1); p.resize(n + 1); w.resize(n + 1); l.resize(n + 1); for(ll i = 1; i <= n; i++){ s[i] = s0[i - 1], p[i] = p0[i - 1], w[i] = w0[i - 1], l[i] = l0[i - 1]; w[i]++, l[i]++; } for(ll i = n; i >= 1; i--) win[i] = win[w[i]] + (ll)s[i]; for(ll i = 1; i <= n; i++){ d[i].push_back(l[i]); d[l[i]].push_back(i); } ll step = 0; for(ll i = 1; i <= n; i++) if(!comp[i]) find_comp(i, ++step); vector<ll> st(n + 1), in(n + 1); for(int i = 1; i <= n; i++) in[l[i]]++; for(int i = 1; i <= n; i++){ if(st[comp[i]] == 0 || in[i] == 0) st[comp[i]] = i; } for(ll i = 1; i <= n; i++){ d2[i].push_back(l[i]); } vector<bool> used_comp(step + 1); for(ll i = 1; i <= n; i++){ if(used_comp[comp[i]]) continue; used_comp[comp[i]] = true; ord.clear(); find_loop(st[comp[i]], -1); reverse(ord.begin(), ord.end()); loops[comp[i]] = ord; for(auto j: ord) loop[j] = true; // cout << i << ' ' << (ll)(ord.size()) << endl; // for(auto j: ord) // cout << j << ' '; // cout << endl; for(ll j = 0; j < (ll)(ord.size()); j++){ build(ord[j], 0); par_pos[ord[j]] = j; } for(auto j: ord) tot[comp[i]] += p[j]; pref[comp[i]].resize((ll)(ord.size())); for(ll j = 0; j < (ll)(ord.size()); j++) pref[comp[i]][j] = (j == 0 ? 0 : pref[comp[i]][j - 1]) + p[ord[j]]; for(auto j: ord) loop[j] = false; } } ll get_sum(ll c, ll pos, ll mid){ if(mid == 0 || pref[c].empty()) return 0; ll cnt = 0; if(pos + mid - 1 < (ll)(pref[c].size())){ cnt = pref[c][pos + mid - 1]; if(pos != 0) cnt -= pref[c][pos - 1]; } else{ ll can = (ll)(pref[c].size()) - pos; cnt = pref[c].back(); if(pos != 0) cnt -= pref[c][pos - 1]; ll need = mid - can; cnt += pref[c][need - 1]; } return cnt; } ll cor(ll x, ll z){ while(x != n + 1){ if(z >= s[x]){ z += s[x]; x = w[x]; } else{ z += p[x]; x = l[x]; } } return z; } long long simulate(int x, int z){ x++; if(z >= s[1]) return z + win[x]; if(t[x][0].first != 0){ if(t[x][19].second + z < s[1]){ z += t[x][19].second; for(ll i = 19; i >= 0; i--) if(t[x][i].first != 0) x = t[x][i].first; } else{ for(ll i = 19; i >= 0; i--){ if(z + t[x][i].second < s[1]){ z += t[x][i].second; x = t[x][i].first; } } // one more step: z += t[x][0].second; x = t[x][0].first; } } if(z >= s[1]) return z + win[x]; ll full = tot[comp[x]]; ll need = (s[1] - z) / full; z += full * need; // cout << z << ' ' << x << endl; // cout << tot[comp[x]] << ' ' << full << ' ' << need << endl; ll c = comp[x], pos = par_pos[x]; ll l = 0, r = (ll)(pref[c].size()); while(l < r){ ll mid = (l + r) >> 1; ll cnt = get_sum(c, pos, mid); if(z + cnt >= s[1]) r = mid; else l = mid + 1; } // cout << "LEN " << l << endl; z += get_sum(c, pos, l); // cout << pos << endl; // for(auto i: loops[c]) // cout << i << ' '; // cout << endl; // // cout << z << endl; if(!pref[c].empty()){ pos = (pos + l) % (ll)(pref[c].size()); x = loops[comp[x]][pos]; } return z + win[x]; } /* 3 1 5 5 5 2 1 3 2 2 3 1 0 1 2 17 2 3 */ /* 4 10 16 16 16 16 7 1 3 2 1 3 4 4 1 0 0 2 0 4 0 1 0 5 3 4 2 6 2 1 3 0 3 1 1 1 1 4 4 1 16 16 16 16 7 1 3 2 1 3 4 4 1 0 0 2 0 1 */
#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...