제출 #928086

#제출 시각아이디문제언어결과실행 시간메모리
928086bobbilyking던전 (IOI21_dungeons)C++17
11 / 100
7062 ms276552 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; using ll = long long ; #define A(a) (a).begin(), (a).end() using pl = pair<ll, ll>; using vl = vector<ll>; #define F(i, l, r) for (ll i = (l); i < (r); ++i) #define FD(i, l, r) for (ll i = (l); i > (r); --i) #define K first #define V second // const ll NN = 5e4+10; const ll NN = 4e5+10; const ll SN = 0; // const ll SN = 3200; ll n; ll s[NN], p[NN], w[NN], l[NN]; // We need this, because this lets us win fast. Otherwise ,would take O(n) even when strength >> 1e7 pl ans[NN]; // {minimum strength needed to clear to root, bonus delta } using T = pl; const ll L = 26; pl lift[NN][L]; ll par[NN][L]; constexpr ll INF = 1e18; T f(T a, T b) { if (a.K == INF) return b; if (b.K == INF) return a; T res; res.K = min(a.K, b.K - a.V); res.V = a.V + b.V; return res; } void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) { n = _n; copy(A(_s), s); copy(A(_p), p); copy(A(_w), w); copy(A(_l), l); // precomp ans FD(i, n-1, -1) { ans[i].K = max(s[i], ans[w[i]].K - s[i]); ans[i].V = ans[w[i]].V + s[i]; } F(i, 0, n) { if (s[i] > SN) { par[i][0] = l[i]; lift[i][0] = {s[i], p[i]}; } else { // when strength > SN, we always win here, so fix these to be winning edge. par[i][0] = w[i]; lift[i][1] = {s[i], s[i]}; } } F(i, 0, L) lift[n][i] = {1e18, 0}; F(l, 1, L) F(i, 0, n) { par[i][l] = par[par[i][l-1]][l-1]; lift[i][l] = f(lift[i][l-1], lift[par[i][l-1]][l-1]); } // F(i, 0, n) { // F(l, 0, L) cout << lift[i][l].K << " " << lift[i][l].V << " | "; // cout << endl; // } } long long simulate(int _x, int _z) { ll x = _x, z = _z; auto iterate1 = [&]{ if (z >= s[x]) z += s[x], x = w[x]; else z += p[x], x = l[x]; }; while (x != n and z <= SN) { iterate1(); } if (x == n) return z; // TODO: implement some kind of bsearch dictating how far to go while taking // only "losing" edges // cout << "Currently: " << x << " " << z << endl; while (1) { if (ans[x].K <= z) return ans[x].V + z; // cout << "Started with " << x << " " << z << endl; // figure out where to jump, then update x and z. We are now at a winning node. FD(l, L-1, -1) { const auto &[thresh, sm] = lift[x][l]; // if (l == 1) { // cout << "Why not jump here? " << endl; // cout << thresh << " " << sm << " | " << z << endl; // auto [a1, b1] = lift[0][0]; // auto [a2, b2] = lift[1][0]; // cout << a1 << " " << b1 << " " << a2 << " " << b2 << endl; // } if (z < thresh) { x = par[x][l]; z += sm; // cout << "Jumped " << l << endl; } } if (x == n) return z; // iterate1(); // cout << "WTF " << x << " " << z << " " << s[x] << endl; // assert(s[x] > SN); assert(z >= s[x]); iterate1(); } }
#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...