Submission #856458

#	Time	Username	Problem	Language	Result	Execution time	Memory
856458		andrei_boaca	Dungeons Game (IOI21_dungeons)	C++17	62 / 100	7015 ms	1084076 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n,s[400005],p[400005],w[400005],l[400005],smax;
bool sub2=0,sub4=0;
vector<ll> mys;
struct date
{
    ll maxim,poz,suma;
} dp[400005][22],whereL[400005],whereR[400005];
ll getver(ll x)
{
    for(int i=0;i<mys.size();i++)
        if(mys[i]>x)
            return i;
    return mys.size();
}
pll ver[7][400005][22]; // {suma,poz}
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];
        mys.push_back(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];
    }
    sort(mys.begin(),mys.end());
    mys.erase(unique(mys.begin(),mys.end()),mys.end());
    w[n]=n;
    if(mys.size()<=5)
    {
        sub4=1;
        for(int v=0;v<=mys.size();v++)
        {
            ll lim=1e9;
            if(v<mys.size())
                lim=mys[v];
            for(int i=0;i<=20;i++)
                ver[v][n][i]={0,n};
            for(int i=0;i<n;i++)
            {
                if(s[i]>=lim)
                {
                    ver[v][i][0].first=p[i];
                    ver[v][i][0].second=l[i];
                }
                else
                {
                    ver[v][i][0].first=s[i];
                    ver[v][i][0].second=w[i];
                }
            }
            for(int j=1;j<=20;j++)
            {
                for(int i=0;i<n;i++)
                {
                    int poz=ver[v][i][j-1].second;
                    ver[v][i][j].second=ver[v][poz][j-1].second;
                    ver[v][i][j].first=ver[v][i][j-1].first+ver[v][poz][j-1].first;
                }
            }
        }
    }
    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(sub4)
    {
        while(x!=n)
        {
            ll v=getver(rez);
            for(ll j=20;j>=0;j--)
                if(getver(ver[v][x][j].first+rez)==v)
                {
                    rez+=ver[v][x][j].first;
                    x=ver[v][x][j].second;
                }
            if(x==n)
                break;
            if(rez>=s[x])
            {
                rez+=s[x];
                x=w[x];
            }
            else
            {
                rez+=p[x];
                x=l[x];
            }
        }
        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;
}

Compilation message (stderr)

dungeons.cpp: In function 'll getver(ll)':
dungeons.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<mys.size();i++)
      |                 ~^~~~~~~~~~~
dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int v=0;v<=mys.size();v++)
      |                     ~^~~~~~~~~~~~
dungeons.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             if(v<mys.size())
      |                ~^~~~~~~~~~~

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