| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1232872 | a4n_ | 던전 (IOI21_dungeons) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
const int N = 4e5 + 100, lg = 25;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
ll MOD(ll a, ll mod=Mod) {
a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
ll res = 1;
while(b > 0) {
if(b%2 == 1) res = MOD(res * a, mod);
b /= 2;
a = MOD(a * a, mod);
}
return res;
}
int t, n, s[N], p[N], w[N], l[N];
ll dp[N];
struct node {
int dest, sump, mx;
node() {
dest = sump = mx = 0;
}
} par[lg][lg][N];
pii move(int x, int z) {
if(z >= s[x]) return {w[x], z + s[x]};
return {l[x], z + p[x]};
}
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
n = _n;
for(int i=1; i<=n; i++) {
s[i] = _s[i-1], p[i] = _p[i-1], w[i] = _w[i-1] + 1, l[i] = _l[i-1] + 1;
}
w[n + 1] = n + 1;
l[n + 1] = n + 1;
for(int i=n; i>=1; i--) {
dp[i] = dp[w[i]] + s[i];
}
for(int i=1; i<=n+1; i++) {
for(int j=0; j<lg; j++) {
if(s[i] < (1<<j)) {
par[0][j][i].dest = w[i];
par[0][j][i].mx = 1e7;
par[0][j][i].sump = s[i];
} else {
par[0][j][i].dest = l[i];
par[0][j][i].mx = s[i] - 1;
par[0][j][i].sump = p[i];
}
}
}
for(int i=1; i<lg; i++) {
for(int j=0; j<lg; j++) {
for(int k=1; k<=n+1; k++) {
par[i][j][k].dest = par[i-1][j][par[i-1][j][k].dest].dest;
par[i][j][k].mx = min(par[i-1][j][k].mx, par[i-1][j][par[i-1][j][k].dest].mx - par[i-1][j][k].sump);
par[i][j][k].sump = par[i-1][j][k].sump + par[i-1][j][par[i-1][j][k].dest].sump;
}
}
}
}
long long simulate(int x, int z) {
x ++;
while(x <= n && z <= 256) {
pii tmp = move(x, z);
x = tmp.F, z = tmp.S;
}
while(x <= n) {
int wh = min(__lg(z), lg - 1);
for(int i=wh; i>=0; i--) {
if(z <= par[i][wh][x].mx) {
z += par[i][wh][x].sump;
x = par[i][wh][x].dest;
}
}
pii tmp = move(x, z);
x = tmp.F, z = tmp.S;
if(z >= 1e7) return (ll)dp[x] + z;
// if(__lg(z) == )
}
return z;
}