oj.uz

Submission #896268

# Submission time Handle Problem Language Result Execution time Memory
896268 2024-01-01T07:01:04 Z MuhammadSaram Dungeons Game (IOI21_dungeons) C++17
37 / 100
 481 ms 389460 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 32 ms 51792 KB Output is correct
5 Correct 3 ms 4696 KB Output is correct
6 Correct 38 ms 51884 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 474 ms 389432 KB Output is correct
3 Correct 481 ms 389432 KB Output is correct
4 Correct 380 ms 389452 KB Output is correct
5 Correct 359 ms 389460 KB Output is correct
6 Correct 426 ms 389436 KB Output is correct
7 Correct 386 ms 389428 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 474 ms 389432 KB Output is correct
3 Correct 481 ms 389432 KB Output is correct
4 Correct 380 ms 389452 KB Output is correct
5 Correct 359 ms 389460 KB Output is correct
6 Correct 426 ms 389436 KB Output is correct
7 Correct 386 ms 389428 KB Output is correct
8 Incorrect 2 ms 4700 KB Output isn't correct
9 Halted 0 ms 0 KB -