Submission #1276412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276412		MMihalev	Dungeons Game (IOI21_dungeons)	C++20	50 / 100	7088 ms	300760 KiB

dungeons

#include<iostream>
#include<algorithm>
#include <vector>
#include<cmath>
using namespace std;
const int MAX_N=4e5+5;
const int LOG=20;
const long long INF=(1LL<<62);
vector<int>wg[MAX_N];
vector<int>lg[MAX_N];
int _s[MAX_N];
int _p[MAX_N];
int _w[MAX_N];
int _l[MAX_N];
int _n;

int wparent[MAX_N][LOG];
int lparent[MAX_N][LOG];
int wdep[MAX_N];
int ldep[MAX_N];
long long wdepth[MAX_N];
long long ldepth[MAX_N];
long long wmax[MAX_N][LOG];
long long lmin[MAX_N][LOG];

int depthtocycle[MAX_N];
vector<vector<int>>cycles;
vector<vector<long long>>cyclemin[LOG];
int posincycle[MAX_N];
int whichcycle[MAX_N];
int cyclecnt;
bool used[MAX_N];
void ldfs(int u)
{
    used[u]=1;
    for(int j=1;j<LOG;j++)
    {
        lparent[u][j]=lparent[lparent[u][j-1]][j-1];
        lmin[u][j]=min(lmin[u][j-1],lmin[lparent[u][j-1]][j-1]);
    }

    for(int v:lg[u])
    {
        if(used[v])continue;

        depthtocycle[v]=depthtocycle[u]+(posincycle[v]!=-1);

        ldep[v]=ldep[u]+1;
        ldepth[v]=ldepth[u]+_p[v];
        lparent[v][0]=u;
        lmin[v][0]=_s[v]+ldepth[v];
        ldfs(v);
    }
}

void wdfs(int u)
{
    for(int j=1;j<LOG;j++)
    {
        wparent[u][j]=wparent[wparent[u][j-1]][j-1];
        wmax[u][j]=max(wmax[u][j-1],wmax[wparent[u][j-1]][j-1]);
    }

    for(int v:wg[u])
    {
        wdep[v]=wdep[u]+1;
        wdepth[v]=wdepth[u]+_s[v];
        wparent[v][0]=u;
        wmax[v][0]=_s[v]+wdepth[v];
        wdfs(v);
    }
}

bool counted[MAX_N];
int findcycledfs(int u,int par)
{
    counted[u]=1;
    for(int v:lg[u])
    {
        if(v==par)continue;

        if(counted[v])
        {
            return u;
        }
        int res=findcycledfs(v,u);
        if(res!=-1)return res;
    }
    return -1;
}

int lg2[2*MAX_N+3];
long long range(int cyclenum,int l,int r)
{
    return (-(cyclemin[0][cyclenum][r]-_s[cycles[cyclenum][r]]))+(cyclemin[0][cyclenum][l]-_s[cycles[cyclenum][l]]);
}
long long query(int cyclenum,int l,int r)
{
    int sz=r-l+1;
    int k=lg2[sz];
    if(cyclemin[k][cyclenum][l]<cyclemin[k][cyclenum][r-(1<<k)+1])
    {
        return cyclemin[k][cyclenum][l];
    }
    return cyclemin[k][cyclenum][r-(1<<k)+1];
}
void solvecomponent(int u)
{
    if(u==_n+1)
    {
        ldfs(u);
        return;
    }

    cyclecnt++;
    u=findcycledfs(u,0);
    vector<int>cycle;
    cycle.push_back(u);
    int v=_l[u];
    while(v!=u)
    {
        cycle.push_back(v);
        v=_l[v];
    }

    int sz=cycle.size();
    for(int i=0;i<sz;i++)
    {
        cycle.push_back(cycle[i]);
    }

    cycles.push_back(cycle);

    long long cur=0;
    cyclemin[0].emplace_back();
    cyclemin[0][cyclecnt-1].resize(cycle.size());
    for(int i=0;i<cycle.size();i++)
    {
        if(posincycle[cycle[i]]==-1)
        {
            whichcycle[cycle[i]]=cyclecnt-1;
            posincycle[cycle[i]]=i;
        }

        cyclemin[0][cyclecnt-1][i]=_s[cycle[i]]-cur;
        cur+=_p[cycle[i]];
    }

    for(int j=1;j<LOG;j++)
    {
        cyclemin[j].emplace_back();
        cyclemin[j][cyclecnt-1].resize(cycle.size());

        for(int i=0;i+(1<<j)-1<cycle.size();i++)
        {
            if(cyclemin[j-1][cyclecnt-1][i]<cyclemin[j-1][cyclecnt-1][i+(1<<(j-1))])
            {
                cyclemin[j][cyclecnt-1][i]=cyclemin[j-1][cyclecnt-1][i];
            }
            else
            {
                cyclemin[j][cyclecnt-1][i]=cyclemin[j-1][cyclecnt-1][i+(1<<(j-1))];
            }
        }
    }

    ldfs(u);
}
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
    _n=N;
    cyclecnt=0;
    cycles.clear();
    for(int j=0;j<LOG;j++)
    {
        cyclemin[j].clear();
    }
    for(int i=1;i<=_n+1;i++)
    {
        ldep[i]=0;
        wdep[i]=0;
        wdepth[i]=0;
        ldepth[i]=0;
        lg[i].clear();wg[i].clear();
        used[i]=0;counted[i]=0;
        depthtocycle[i]=0;
    }
    for(int i=1;i<=2*_n;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];
        wg[_w[i]].push_back(i);
        lg[_l[i]].push_back(i);
        lg[i].push_back(_l[i]);
        posincycle[i]=-1;
    }
    posincycle[_n+1]=-1;

    wdfs(_n+1);

    for(int i=_n+1;i>=1;i--)
    {
        if(!used[i])
        {
            solvecomponent(i);
        }
    }
}
void firstwin(int&x,long long&cur)
{
    for(int j=LOG-1;j>=0;j--)
    {
        if(ldep[x]-(1<<j)<depthtocycle[x])continue;
        if(lmin[x][j]>cur+ldepth[x])
        {
            cur+=ldepth[x];
            x=lparent[x][j];
            cur-=ldepth[x];
        }
    }

    if(x==_n+1)return;

    if(cur>=_s[x])return;

    int cyclenum=whichcycle[x];
    int pos=posincycle[x];

    long long mi=query(cyclenum,pos,pos+cycles[cyclenum].size()/2-1);
    if(cur+(cyclemin[0][cyclenum][pos]-_s[cycles[cyclenum][pos]])<mi)
    {
        long long sum=range(cyclenum,pos,pos+cycles[cyclenum].size()/2);
        long long times=(mi-(cur+(cyclemin[0][cyclenum][pos]-_s[cycles[cyclenum][pos]]))+sum-1)/sum;
        cur+=times*sum;
    }

    int ending=pos+cycles[cyclenum].size()/2-1;
    for(int j=LOG-1;j>=0;j--)
    {
        if(pos+(1<<j)>ending)continue;
        if(cyclemin[j][cyclenum][pos]>(cyclemin[0][cyclenum][pos]-_s[cycles[cyclenum][pos]]+cur))
        {
            cur+=range(cyclenum,pos,pos+(1<<j));
            pos+=(1<<j);
        }
    }
    x=cycles[cyclenum][pos];
}
void firstlose(int&x,long long&cur)
{
    for(int j=LOG-1;j>=0;j--)
    {
        if(wdep[x]-(1<<j)<0)continue;
        if(wmax[x][j]<=cur+wdepth[x])
        {
            cur+=wdepth[x];
            x=wparent[x][j];
            cur-=wdepth[x];
        }
    }
}
long long simulate(int x, int z)
{
    x++;
    long long cur=z;
    long long initz=z,initx=x,begz=z,begx=x;

    while(x!=_n+1)
    {
        if(cur<_s[x])
        {
            firstwin(x,cur);
        }
        else
        {
            firstlose(x,cur);
        }
    }return cur;

    while(begx!=_n+1)
    {
        if(begz<_s[begx])
        {
            begz+=_p[begx];
            begx=_l[begx];
        }
        else
        {
            begz+=_s[begx];
            begx=_w[begx];
        }
    }

    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: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11