Submission #1205266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205266		simona1230	Dungeons Game (IOI21_dungeons)	C++20	25 / 100	7100 ms	191364 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=5*1e4+5;
const int logg=30;
int n;
vector<int> s,p,w,l,h;
vector<long long> v;
int c,done[maxn];
long long sum[maxn][32][10];
int ver[maxn][32][10];

int construct(long long x)
{
    if(done[x])return done[x];
    c++;
    done[x]=c;
    x=v[x];
    for(int i=0; i<n; i++)
    {
        if(x>s[i])
        {
            ver[i][0][c]=w[i];
            sum[i][0][c]=s[i];
        }
        else
        {
            ver[i][0][c]=l[i];
            sum[i][0][c]=p[i];
        }
    }
    ver[n][0][c]=n;

    for(int j=1; j<=logg; j++)
        for(int i=0; i<=n; i++)
        {
            sum[i][j][c]=sum[i][j-1][c]+sum[ver[i][j-1][c]][j-1][c];
            if(1e18-sum[i][j-1][c]<sum[ver[i][j-1][c]][j-1][c])sum[i][j][c]=1e18;
            ver[i][j][c]=ver[ver[i][j-1][c]][j-1][c];
            //cout<<ver[i][j][num]<<" "<<i<<" "<<(1<<j)<<endl;
        }
    return c;

}

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;

    h=s;
    sort(h.begin(),h.end());
    v= {h[0]};
    for(int i=1; i<h.size(); i++)
        if(h[i]!=h[i-1])v.push_back(h[i]);
    v.push_back(1e18);
    return;
}

long long simulate(int x, int zz)
{
    long long z=zz;
    long long num=0;

    while(num<v.size()&&x!=n)
    {
        while(num<v.size()&&z>=v[num])num++;
        //cout<<x<<" "<<z<<" "<<v[num]<<endl;
        int i=construct(num);

        for(int j=logg;j>=0;j--)
        {
            if(z<v[num]-sum[x][j][i])
            {
                z+=sum[x][j][i];
                x=ver[x][j][i];
            }
        }
        if(x==n)return z;
        z+=sum[x][0][i];
        x=ver[x][0][i];
    }

    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;
        }
    }
}*/

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