제출 #1057559

#제출 시각아이디문제언어결과실행 시간메모리
1057559Trent던전 (IOI21_dungeons)C++17
63 / 100
7052 ms1802072 KiB
#include "dungeons.h" #include "bits/stdc++.h" using namespace std; #define forR(i, x) for(int i = 0; i < (x); ++i) #define REP(i, a, b) for(int i = (a); i < (b); ++i) typedef long long ll; typedef vector<int> vi; int n; vi s, p, w, l; const int VLS = 30, ME = 7, MN = 4e5 + 10; vi skp; // thl becomes int struct ch{int t; ll by; int thl;}; ch bjp[VLS][MN][ME]; const int INF = 1e8; int trunc(ll val, int lo, int hi) { return (int) max((ll) lo, min((ll) hi, val)); } void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) { ::n=n; ::s=s, ::p=p, ::w=w, ::l=l; skp.push_back(0); REP(i, 1, VLS) skp.push_back(1 << (i-1)); forR(si, VLS) { int val = skp[si]; forR(i, n) { if(s[i] <= val) bjp[si][i][0] = {w[i], (ll) s[i], INF}; else bjp[si][i][0] = {l[i], (ll) p[i], s[i]}; } REP(e, 1, ME) { forR(i, n) { bjp[si][i][e] = bjp[si][i][e-1]; forR(j, 15) { ch nex = bjp[si][i][e]; if(nex.t == n) bjp[si][i][e] = nex; else { int nth = bjp[si][nex.t][e-1].thl == INF ? INF : trunc(bjp[si][nex.t][e-1].thl - nex.by, -1, INF); bjp[si][i][e] = {bjp[si][nex.t][e-1].t, bjp[si][nex.t][e-1].by + nex.by, min(nex.thl, nth)}; } } } } } } struct pii{int a; ll b;}; pii tWin(int x, ll z, int igi) { assert(z >= skp[igi]); int ci=x; ll cv = z; for(int e = ME - 1; e >= 0; --e) { if(ci == n) return {ci, cv}; while(bjp[igi][ci][e].thl == INF || cv < bjp[igi][ci][e].thl) { cv += bjp[igi][ci][e].by; ci = bjp[igi][ci][e].t; if(ci == n) return {ci, cv}; } } return {ci, cv}; } long long simulate(int x, int z) { int ci = x; ll cv = z; forR(ind, VLS) { pii nex = tWin(ci, cv, ind); if(nex.a == n) { return nex.b; } ci=nex.a; cv=nex.b; assert(cv >= s[ci]); cv += s[ci]; ci = w[ci]; } return cv; }
#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...