Submission #1232619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232619		LeonidCuk	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7091 ms	268932 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>w,l,s,p;
struct pom{
	long long sum=0,smax=0,nxt=0;
};
vector<vector<pom>>lca;
void init(int N,vector<int> S,vector<int> P,vector<int> W,vector<int> L) {
	n=N;
	l=L;
	s=S;
	p=P;
	w=W;
	lca.resize(n+1,vector<pom>(25));
	s.push_back(0);
	l.push_back(n);
	w.push_back(n);
	p.push_back(0);
	for(int j=0;j<25;j++)
	{
		for(int i=0;i<=n;i++)
		{
			if(j==0)
			{
				lca[i][j].nxt=w[i];
				lca[i][j].sum=s[i];
				lca[i][j].smax=s[w[i]]-s[i];
			}
			else
			{
				int a=lca[i][j-1].nxt;
				lca[i][j].nxt=lca[a][j-1].nxt;
				lca[i][j].sum=lca[i][j-1].sum+lca[a][j-1].sum;
				lca[i][j].smax=max(lca[i][j-1].smax,lca[a][j-1].smax-lca[i][j-1].sum);
			}
		}
	}
	return;
}

long long simulate(int x, int z) {
	long long sum=z;
	while(x!=n)
	{
		if(sum>=s[x])
		{
			
			for(int i=24;i>=0;i--)
			{
				if(sum>=lca[x][i].smax)
				{
					sum+=lca[x][i].sum;
					x=lca[x][i].nxt;
				}
			}
			sum+=s[x];
			x=w[x];
		}
		else
		{
			sum+=p[x];
			x=l[x];
		}
	}
	return sum;
}

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