| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1276661 | MMihalev | Dungeons Game (IOI21_dungeons) | C++20 | 0 ms | 0 KiB |
#include<iostream>
#include<algorithm>
#include <vector>
#include<cmath>
using namespace std;
const int MAX_N=4e5+5;
const long long MAX=1e7+MAX_N;
const int LOG=24;
const int REMLOG=11;
const int CC=1024;
const long long INF=(1LL<<62);
int _s[MAX_N];
int _p[MAX_N];
int _w[MAX_N];
int _l[MAX_N];
int _n;
int parent[REMLOG][MAX_N][LOG];
int wparent[MAX_N][LOG];
long long wsum[MAX_N][LOG];
long long sum[REMLOG][MAX_N][LOG];
long long minremain[REMLOG][MAX_N][LOG];
int lg2[MAX_N];
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
_n=N;
for(int i=1;i<=_n+1;i++)
{
lg2[i]=(int)log2(i);
}
for(int i=1;i<=_n;i++)
{
W[i-1]++;L[i-1]++;
_s[i]=S[i-1];
_p[i]=P[i-1];
_w[i]=W[i-1];
_l[i]=L[i-1];
}
int sparsenum=0;
for(long long cost=CC;cost<=MAX;cost*=2LL)
{
for(int i=1;i<=_n;i++)
{
if(_s[i]>cost)
{
parent[sparsenum][i][0]=_l[i];
sum[sparsenum][i][0]=_p[i];
minremain[sparsenum][i][0]=_s[i];
}
else
{
parent[sparsenum][i][0]=_w[i];
sum[sparsenum][i][0]=_s[i];
minremain[sparsenum][i][0]=INF;
}
}
for(int j=1;j<LOG;j++)
{
for(int i=1;i<=_n;i++)
{
parent[sparsenum][i][j]=parent[sparsenum][parent[sparsenum][i][j-1]][j-1];
sum[sparsenum][i][j]=sum[sparsenum][i][j-1]+sum[sparsenum][parent[sparsenum][i][j-1]][j-1];
minremain[sparsenum][i][j]=min(minremain[sparsenum][i][j-1],(minremain[sparsenum][parent[sparsenum][i][j-1]][j-1]==INF ? INF : max(0LL,minremain[sparsenum][parent[sparsenum][i][j-1]][j-1]-sum[sparsenum][i][j-1])));
}
}
sparsenum++;
}
for(int i=1;i<=_n;i++)
{
wparent[i][0]=_w[i];
wsum[i][0]=_s[i];
}
for(int j=1;j<LOG;j++)
{
for(int i=1;i<=_n;i++)
{
wparent[i][j]=wparent[wparent[i][j-1]][j-1];
wsum[i][j]=wsum[i][j-1]+wsum[wparent[i][j-1]][j-1];
}
}
}
long long simulate(int x, int z)
{
x++;
long long cur=z;
long long initz=z,initx=x,begz=z,begx=x;
while(cur<CC)
{
if(cur<_s[x])
{
cur+=_p[x];
x=_l[x];
}
else
{
cur+=_s[x];
x=_w[x];
}
}
int sparsenum=0;
for(long long cost=CC;cost<=MAX;cost*=2LL)
{
if(cost<=cur && cur<2*cost)
{
for(int j=LOG-1;j>=0;j--)
{
//cout<<cost<<" "<<(1<<j)<<" "<<x<<" "<<parent[sparsenum][x][j]<<" "<<sum[sparsenum][x][j]<<" "<<minremain[sparsenum][x][j]<<" "<<cur<<"\n";
if(parent[sparsenum][x][j]==0 or cur+sum[sparsenum][x][j]>=2*cost or minremain[sparsenum][x][j]-cur<=0)continue;
//cout<<cost<<" "<<(1<<j)<<" "<<x<<" "<<cur<<" ";
cur+=sum[sparsenum][x][j];
x=parent[sparsenum][x][j];
//cout<<" "<<x<<" "<<cur<<"\n";
}
}
if(x==_n+1)break;
if(cur<_s[x])
{
cur+=_p[x];
x=_l[x];
}
else
{
cur+=_s[x];
x=_w[x];
}
sparsenum++;
}
for(int j=LOG-1;j>=0;j--)
{
if(wparent[x][j]==0)continue;
cur+=wsum[x][j];
x=wparent[x][j];
}
return cur;
while(begx!=_n+1)
{
if(begz<_s[begx])
{
begz+=_p[begx];
begx=_l[begx];
}
else
{
begz+=_s[begx];
begx=_w[begx];
}
}//return begz;
if(begz!=cur)
{
cout<<_n<<"\n";
for(int i=1;i<=_n;i++)
{
cout<<_s[i]<<" ";
}
cout<<"\n";
for(int i=1;i<=_n;i++)
{
cout<<_p[i]<<" ";
}
cout<<"\n";
for(int i=1;i<=_n;i++)
{
cout<<_w[i]<<" ";
}
cout<<"\n";
for(int i=1;i<=_n;i++)
{
cout<<_l[i]<<" ";
}
cout<<"\n";
cout<<initx<<" "<<initz<<"\n";
exit(0);
}
return cur;
}