Submission #1204738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204738		simona1230	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	272 ms	154052 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,v;
long long sum[maxn][32][8];
int ver[maxn][32][8];
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(1e9);

    for(int num=0; num<v.size(); num++)
    {
        //cout<<v[num]<<"!!"<<endl;
        for(int i=0;i<n;i++)
        {
            if(v[num]>s[i])
            {
                ver[i][0][num]=w[i];
                sum[i][0][num]=s[i];
            }
            else
            {
                ver[i][0][num]=l[i];
                sum[i][0][num]=p[i];
            }
        }
        ver[n][0][num]=n;

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

    return;
}

long long simulate(int x, int zz)
{
    long long z=zz;
    int num=0;
    while(num<v.size()&&z>=v[num])num++;

    while(num<v.size())
    {
        //cout<<x<<" "<<z<<" "<<v[num]<<endl;
        for(int j=logg;j>=0;j--)
        {
            if(z+sum[x][j][num]<v[num])
            {
                z+=sum[x][j][num];
                x=ver[x][j][num];
            }
        }
        if(x==n)return z;
        z+=sum[x][0][num];
        x=ver[x][0][num];
        num++;
    }

    return z;
}

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