Submission #444134

#	Time	Username	Problem	Language	Result	Execution time	Memory
444134		leinad2	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	78 ms	29736 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
int N, i, j, sparse2[400010][20];
long long A[400010], sparse3[400010][20];
vector<int>S, P, W, L;
void init(int n, vector<int>s, vector<int>p, vector<int>w, vector<int>l)
{
    N=n;S=s;P=p;W=w;L=l;W.push_back(N);S.push_back(0);L.push_back(N);P.push_back(0);
    for(i=n-1;i>=0;i--)A[i]=A[W[i]]+S[i];
    for(i=0;i<=n;i++)sparse2[i][0]=L[i],sparse3[i][0]=P[i];
    for(j=1;j<20;j++)for(i=0;i<=n;i++)sparse2[i][j]=sparse2[sparse2[i][j-1]][j-1],sparse3[i][j]=sparse3[i][j-1]+sparse3[sparse2[i][j-1]][j-1];
}
long long simulate(int x, int Z)
{
    long long z=Z, s=S[0];
    if(z<s)
    {
        for(j=19;j>=0;j--)
        {
            if(z+sparse3[x][j]<s)
            {
                z+=sparse3[x][j];
                x=sparse2[x][j];
            }
        }
        z+=P[x];
        x=L[x];
    }
  	if(z<s)
    {
    	for(j=19;j>=0;j--)
        {
        	assert(z+sparse3[x][j]<s);
        }
    }
    z+=A[x];
    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