Submission #1204760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204760		simona1230	Dungeons Game (IOI21_dungeons)	C++20	11 / 100	7093 ms	45088 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;

int maxx[maxn][32];
long long sum[maxn][32];
int ver[maxn][32];

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;

    for(int i=0;i<n;i++)
    {
        maxx[i][0]=s[i];
        sum[i][0]=s[i];
        ver[i][0]=w[i];
    }
    ver[n][0]=n;

    for(int j=1;j<=logg;j++)
    {
        for(int i=0;i<=n;i++)
        {
            maxx[i][j]=max(maxx[i][j-1],maxx[ver[i][j-1]][j-1]);
            sum[i][j]=sum[i][j-1]+sum[ver[i][j-1]][j-1];
            if(1e18-sum[i][j-1]<sum[ver[i][j-1]][j-1])sum[i][j]=1e18;
            ver[i][j]=ver[ver[i][j-1]][j-1];
        }
    }


    return;
}

long long simulate(int x, int zz)
{
    long long z=zz;
    while(1)
    {
        for(int j=logg;j>=0;j--)
        {
            if(maxx[x][j]<=z)
            {
                z+=sum[x][j];
                x=ver[x][j];
                break;
            }
        }

        if(x==n)return z;

        if(z<s[x])
        {
            z+=p[x];
            x=l[x];
        }
        else
        {
            z+=s[x];
            x=w[x];
        }
    }

    return z;
}

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