Submission #896268

#	Time	Username	Problem	Language	Result	Execution time	Memory
896268		MuhammadSaram	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	481 ms	389460 KiB

dungeons

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int M = 4e5+1, lg=20;

ll lose[M][lg+10][2],win[M][lg][3];
int N,ty;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
	N=n;
	set<int> se;
	ty=0;
	for (int i=0;i<n;i++)
	{
		lose[i][0][0]=p[i];
		lose[i][0][1]=l[i];
		se.insert(s[i]);
		win[i][0][0]=win[i][0][1]=s[i],win[i][0][2]=w[i];
	}
	if (se.size()==1)
		ty=1;
	for (int j=1;j<lg;j++)
		for (int i=0;i<n;i++)
		{
			if (win[i][j-1][2]!=n and win[i][j-1][2]!=-1)	
				win[i][j][2]=win[win[i][j-1][2]][j-1][2];
			else
			{
				win[i][j][2]=-1;
				continue;
			}
			win[i][j][0]=max(win[i][j-1][0],win[win[i][j-1][2]][j-1][0]-win[i][j-1][1]);
			win[i][j][1]=win[i][j-1][1]+win[win[i][j-1][2]][j-1][1];
		}
	for (int j=1;j<lg+10;j++)
		for (int i=0;i<n;i++)
		{
			if (lose[i][j-1][1]!=n and lose[i][j-1][1]!=-1)
				lose[i][j][1]=lose[lose[i][j-1][1]][j-1][1];
			else
			{
				lose[i][j][1]=-1;
				continue;
			}
			lose[i][j][0]=lose[i][j-1][0]+lose[lose[i][j-1][1]][j-1][0];
		}
}

long long simulate(int x, int z)
{
	ll ans=z;
	if (ty==0)
	{
		while (x!=N)
		{
			for (int i=lg-1;i>=0 and x!=N;i--)
				if (win[x][i][2]!=-1 and ans>=win[x][i][0])
				{
					ans+=win[x][i][1];
					x=win[x][i][2];
				}
			if (x!=N)
			{
				ans+=lose[x][0][0];
				x=lose[x][0][1];
			}
		}
		return ans;
	}
	ll tar=win[0][0][0];
	for (int i=lg+9;i>=0 and x!=N;i--)
		if (lose[x][i][1]!=-1 and ans+lose[x][i][0]<tar)
		{
			ans+=lose[x][i][0];
			x=lose[x][i][1];
		}
	if (x!=N)
	{
		ans+=lose[x][0][0];
		x=lose[x][0][1];
		for (int i=lg-1;i>=0 and x!=N;i--)
			if (win[x][i][2]!=-1 and ans>=win[x][i][0])
			{
				ans+=win[x][i][1];
				x=win[x][i][2];
			}
	}
	return ans;
}

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