Submission #442079

#	Time	Username	Problem	Language	Result	Execution time	Memory
442079		daniel920712	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	2 ms	1228 KiB

dungeons

#include "dungeons.h"
#include <vector>
using namespace std;
long long con[35][200005];
long long nxt[35][200005];
long long how[200005];
long long fin;
void init(int n,vector < int > s,vector < int > p,vector < int > w,vector < int > l)
{
    int i,j;
    fin=s[0];
    how[n]=0;
    for(i=n-1;i>=0;i--) how[i]=how[w[i]]+1;
    for(i=0;i<n;i++)
    {
        nxt[0][i]=l[i];
        con[0][i]=p[i];
    }
    for(i=1;i<=30;i++)
    {
        for(j=0;j<n;j++)
        {
            nxt[i][j]=nxt[i-1][nxt[i-1][j]];
            con[i][j]=con[i-1][j]+con[i-1][nxt[i-1][j]];
        }
    }
	return;
}

long long simulate(int x, int z)
{
    long long ans=z,now=x,i;
    if(ans>=fin) return ans+how[now]*fin;
    for(i=30;i>=0;i--)
    {
        if(ans+=nxt[i][now]<fin)
        {
            ans+=con[i][now];
            now=nxt[i][now];
        }
    }
    ans+=con[0][now];
    now=nxt[0][now];
    return ans+how[now]*fin;


}

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