Submission #856454

#	Time	Username	Problem	Language	Result	Execution time	Memory
856454		andrei_boaca	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7061 ms	251960 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
ll n,s[400005],p[400005],w[400005],l[400005],smax;
bool sub2=0;
struct date
{
    ll maxim,poz,suma;
} dp[400005][22],whereL[400005],whereR[400005];
date tour(ll poz,ll val)
{
    if(dp[poz][20].maxim<=val)
        return {0,n,dp[poz][20].suma};
    ll suma=0;
    for(ll j=20;j>=0;j--)
        if(dp[poz][j].maxim<=val)
        {
            suma+=dp[poz][j].suma;
            poz=w[dp[poz][j].poz];
        }
    return {0,poz,suma};
}
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
    n=N;
    sub2=1;
    for(int i=0;i<n;i++)
    {
        s[i]=S[i];
        smax=max(smax,s[i]);
        p[i]=P[i];
        if(s[i]!=p[i])
            sub2=0;
        w[i]=W[i];
        l[i]=L[i];
    }
    w[n]=n;
    if(sub2)
    {
        for(int j=0;j<=20;j++)
            dp[n][j]={0,n,0};
        for(int i=n-1;i>=0;i--)
        {
            dp[i][0]={s[i],i,s[i]};
            for(int j=1;j<=20;j++)
            {
                ll p=w[dp[i][j-1].poz];
                ll poz=dp[p][j-1].poz;
                dp[i][j].poz=poz;
                dp[i][j].maxim=max(dp[i][j-1].maxim,dp[p][j-1].maxim);
                dp[i][j].suma=dp[i][j-1].suma+dp[p][j-1].suma;
            }
        }
        for(int i=0;i<n;i++)
        {
            whereL[i]=tour(l[i],s[i]);
            whereR[i]=tour(w[i],s[i]);
        }
    }
}

long long simulate(int x, int z)
{
    ll rez=z;
    if(x==n)
        return rez;
    if(sub2)
    {
        while(x!=n)
        {
            if(rez>=s[x])
            {
                rez+=s[x];
                if(rez>=smax)
                {
                    rez+=dp[w[x]][20].suma;
                    return rez;
                }
                rez+=whereR[x].suma;
                x=whereR[x].poz;
            }
            else
            {
                rez+=s[x];
                if(rez>=smax)
                {
                    rez+=dp[l[x]][20].suma;
                    return rez;
                }
                rez+=whereL[x].suma;
                x=whereL[x].poz;
            }
        }
        return rez;
    }
    while(x!=n)
    {
        if(rez>=s[x])
        {
            rez+=s[x];
            x=w[x];
        }
        else
        {
            rez+=p[x];
            x=l[x];
        }
    }
    return rez;
}

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