| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1205673 | simona1230 | Dungeons Game (IOI21_dungeons) | C++20 | 0 ms | 0 KiB |
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=4*1e5+5;
const int logg=19;
const int base=4;
int n;
vector<int> s,p,w,l,h;
vector<long long> v;
int c,done[maxn];
long long sum[maxn][20][15];
int ver[maxn][20][15];
long long lim[maxn][20][15];
void construct(int x)
{
//cout<<x<<"! "<<endl;
for(int i=0; i<n; i++)
{
if(v[x]>=s[i])
{
ver[i][0][x]=w[i];
sum[i][0][x]=s[i];
lim[i][0][x]=1e18;
}
else
{
ver[i][0][x]=l[i];
sum[i][0][x]=p[i];
lim[i][0][x]=s[i];
}
}
ver[n][0][x]=n;
lim[n][0][x]=1e18;
for(int j=1; j<=logg; j++)
for(int i=0; i<=n; i++)
{
sum[i][j][x]=sum[i][j-1][x]+sum[ver[i][j-1][x]][j-1][x];
if(1e18-sum[i][j-1][x]<sum[ver[i][j-1][x]][j-1][x])sum[i][j][x]=1e18;
ver[i][j][x]=ver[ver[i][j-1][x]][j-1][x];
long long here=lim[ver[i][j-1][x]][j-1][x]-sum[i][j-1][x];
if(lim[ver[i][j-1][x]][j-1][x]==1e18)here=1e18;
lim[i][j][x]=min(lim[i][j-1][x],here);
//cout<<i<<" "<<j<<" "<<x<<" "<<ver[i][j][x]<<" "<<sum[i][j][x]<<" "<<lim[i][j][x]<<endl;
}
}
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;
int pw=1;
v={1};
while(pw*base<=1e7)
{
pw*=base;
v.push_back(pw);
}
v.push_back(1e18);
for(int i=0;i<v.size();i++)
construct(i);
return;
}
long long simulate(int x, int zz)
{
long long z=zz;
long long num=0;
int in=0;
while(num<v.size()&&x!=n)
{
in++;
if(in>50)return 0;
while(num+1<v.size()&&z>=v[num+1])num++;
//cout<<x<<" - "<<z<<" "<<num<<endl;
for(int j=logg;j>=0;j--)
{
//cout<<x<<" "<<j<<" "<<num<<" "<<lim[x][j][num]<<endl;
if(z<lim[x][j][num])
{
z+=sum[x][j][num];
x=ver[x][j][num];
}
}
//cout<<x<<" "<<x<<endl;
if(x==n)return z;
z+=s[x];
x=w[x];
}
return z;
}
/*int main()
{
while(1)
{
int nn=100;
vector<int> ss,pp,ww,ll;
int r=1e7;
for(int i=0;i<nn;i++)
ss.push_back(r);
for(int i=0;i<nn;i++)
pp.push_back(rand()%10);
for(int i=0;i<nn;i++)
ww.push_back(min(nn,rand()%2+1+i));
for(int i=0;i<nn;i++)
ll.push_back(rand()%(nn+1));
init(nn,ss,pp,ww,ll);
cout<<nn<<" "<<5<<endl;
for(int i=0;i<ss.size();i++)
cout<<ss[i]<<" ";
cout<<endl;
for(int i=0;i<pp.size();i++)
cout<<pp[i]<<" ";
cout<<endl;
for(int i=0;i<ww.size();i++)
cout<<ww[i]<<" ";
cout<<endl;
for(int i=0;i<ll.size();i++)
cout<<ll[i]<<" ";
cout<<endl;
for(int i=1;i<=5;i++)
{
int xx,zz;
xx=rand()%nn;
zz=rand()%10;
cout<<xx<<" "<<zz<<endl;
cout<<simulate(xx,zz)<<endl;
}
}
}*/