Submission #1276674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276674		MMihalev	Dungeons Game (IOI21_dungeons)	C++20	100 / 100	6358 ms	1965996 KiB

dungeons

#include<iostream>
#include<algorithm>
#include <vector>
#include<cmath>
using namespace std;
const int MAX_N=4e5+5;
const int MAX=1e7+MAX_N;
const int LOG=23;
const int REMLOG=17;
const int CC=128;
const long long INF=(1LL<<62);
const int INT_INF=1e9;

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];
int sum[REMLOG][MAX_N][LOG];
int 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(int cost=CC;cost<=MAX;cost*=2)
    {
        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]=INT_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]=min(INT_INF,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]==INT_INF ? INT_INF : max(0,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];
        }

        if(x==_n+1)return cur;
    }

    int sparsenum=0;
    for(int cost=CC;cost<=MAX;cost*=2)
    {
        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+1LL*sum[sparsenum][x][j]>=2*cost or 1LL*minremain[sparsenum][x][j]<=cur)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;
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11