| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1299310 | Faisal_Saqib | Dungeons Game (IOI21_dungeons) | C++20 | 0 ms | 0 KiB |
// #include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=4e5+1,LG=25;
const ll inf=1e18;
ll n,s[N],p[N],w[N],l[N];
ll nxt[LG][N][LG],inc[LG][N][LG],th[LG][N][LG];
void init(int n2, std::vector<int> s1, std::vector<int> p1, std::vector<int> w1, std::vector<int> l1)
{
n=n2;
for(int i=0;i<n;i++)
{
s[i]=s1[i];
p[i]=p1[i];
w[i]=w1[i];
l[i]=l1[i];
}
s[n]=p[n]=0;
w[n]=l[n]=n;
for(int k=0;k<LG;k++)
{
ll pw=1ll<<k;
// assume 2^k <= z < 2^(k+1)
// for all si < 2^k we win
for(int j=0;j<=n;j++)
{
if(s[j]<=pw)
{
nxt[k][j][0]=w[j];
inc[k][j][0]=s[j];
th[k][j][0]=inf;
}
else
{
nxt[k][j][0]=l[j];
inc[k][j][0]=p[j];
th[k][j][0]=s[j];
// if z>=th[j] then we could have won at stage
}
}
for(int j=1;j<LG;j++)
{
for(int i=0;i<=n;i++)
{
nxt[k][i][j]=nxt[k][nxt[k][i][j-1]][j-1];
inc[k][i][j]=inc[k][i][j-1] + inc[k][nxt[k][i][j-1]][j-1];
th[k][i][j]=min(th[k][i][j-1],th[k][nxt[k][i][j-1]][j-1] - inc[k][i][j-1]);
}
}
}
}
long long simulate(int x1, int z1)
{
long long z=z1,x=x1;
ll pw=1,lg=0;
while(x!=n)
{
while((pw*2)<=z)
{
pw*=2;
lg++;
}
lg=min(lg,24ll);
for(int j=LG-1;j>=0;j--)
{
if(th[lg][x][j]>z) // we dont win
{
z+=inc[lg][x][j];
x=nxt[lg][x][j];
}
}
if(s[x]<=z)
{
z+=s[x];
x=w[x];
}
else
{
z+=p[x];
x=l[x];
}
}
return z;
}