Submission #454732

#	Time	Username	Problem	Language	Result	Execution time	Memory
454732		ogibogi2004	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	2 ms	716 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int MAXN=4e5+6;
int g1[MAXN];
int g2[MAXN];
int dp1[MAXN][20];
int dp2[MAXN][20];
int p1[MAXN][20];
int p2[MAXN][20];
int strength[MAXN];
int points[MAXN],n1;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	for(int i=0;i<n;i++)
	{
		points[i]=p[i];
		strength[i]=s[i];
		g1[i]=l[i];
		g2[i]=w[i];
		dp1[i][0]=g1[i];
		dp2[i][0]=g2[i];
		p1[i][0]=points[i];
		p2[i][0]=strength[i];
	}
	n1=n;
	for(int step=1;step<20;++step)
	{
		for(int i=0;i<n;++i)
		{
			if(dp1[i][step-1]==n||dp1[i][step-1]==n+1)dp1[i][step]=n+1;
			else dp1[i][step]=dp1[dp1[i][step-1]][step-1];
			p1[i][step]=p1[i][step-1]+p1[dp1[i][step-1]][step-1];
			if(dp2[i][step-1]==n||dp2[i][step-1]==n+1)dp2[i][step]=n+1;
			else dp2[i][step]=dp2[dp2[i][step-1]][step-1];
			p2[i][step]=p2[i][step-1]+p2[dp2[i][step-1]][step-1];
		}
	}
	return;
}

long long simulate(int x, int z) {
	if(z>=strength[0])
	{
		for(int i=19;i>=0;i--)
		{
			if(x==n1)continue;
			if(dp2[x][i]!=n1+1)
			{
				z+=p2[x][i];
				x=dp2[x][i];
			}
		}
		if(x!=n1)assert(false);
		return z;
	}
	else
	{
		for(int i=19;i>=0;i--)
		{
			if(dp1[x][i]==n1+1)continue;
			if(z+p1[x][i]<strength[0])
			{
				z+=p1[x][i];
				x=dp1[x][i];
			}
		}
		//cout<<x<<" "<<z<<endl;
		z+=points[x];
		x=g1[x];
		//cout<<x<<" "<<z<<endl;
		for(int i=19;i>=0;i--)
		{
			if(x==n1)continue;
			if(dp2[x][i]!=n1+1)
			{
				z+=p2[x][i];
				x=dp2[x][i];
			}
		}
		if(x!=n1)assert(false);
		return z;
	}
	return 0;
}

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