Submission #1211759

#TimeUsernameProblemLanguageResultExecution timeMemory
1211759ksu2009enDungeons Game (IOI21_dungeons)C++20
26 / 100
445 ms259500 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){ if(!t[v][0].first) t[v][0].first = par; if(t[v][0].first != 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); } } ll st[(ll)(5e4 + 7)]; bool group3 = true, group2 = true; ll t2[(ll)(4e5 + 7)][20][3]; vector<int> d3[(ll)(4e5 + 7)]; void build_t2(ll v, ll par){ t2[v][0][0] = par; t2[v][0][1] = t2[v][0][2] = s[v]; for(int i = 1; i < 20; i++){ t2[v][i][0] = t2[t2[v][i - 1][0]][i - 1][0]; t2[v][i][1] = t2[v][i - 1][1] + t2[t2[v][i - 1][0]][i - 1][1]; t2[v][i][2] = max(t2[v][i - 1][2], t2[t2[v][i - 1][0]][i - 1][2]); } for(auto i: d3[v]) if(i != par) build_t2(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.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(int i = 1; i <= n; i++){ if(s[i] != s[1]) group3 = false; if(s[i] != p[i]) group2 = false; } if(group2){ for(int i = 1; i <= n; i++) d3[w[i]].push_back(i); build_t2(n + 1, 0); return; } } 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(!group3 && !group2) return cor(x, z); if(group2){ while(x != n + 1){ for(int i = 19; i >= 0; i--){ if(t2[x][i][0] != 0 && z >= t2[x][i][2]){ z += t2[x][i][1]; x = t2[x][i][0]; } } if(x != n + 1 && z < s[x]){ z += s[x]; x = l[x]; } } return z; } return 0; } /* 4 1 3 5 2 1 3 5 2 1 1 3 3 4 0 3 2 1 0 4 2 5 */
#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...