Submission #1049104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049104		parsadox2	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	7070 ms	399880 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

const int N = 4e5 + 10 , Lg = 20;
const long long inf = 1e15 + 10;

int n;

vector <int> s , p , w , l;

long long f(long long x)
{
	if(x <= 0)
		return inf;
	return x;
}

struct item{
	long long mn;
	long long val;
	int id;
};

item a[2 * N][Lg];

item Get(item now , int len)
{
	if(len == 0)
		return now;
	long long id = now.id , mn = now.mn , val = now.val , dif = val - (val >= s[id]) * s[id];

	for(int i = Lg - 1 ; i >= 0 ; i--)  if((1 << i) <= len && a[id * 2 + (val >= s[id])][i].mn > dif)
	{
		item tmp = a[id * 2 + (val >= s[id])][i];
		return Get({min(mn , tmp.mn - dif) , tmp.val + dif , tmp.id} , len - (1 << i));
	}
	if(val >= s[id])
		return Get({min(mn , f(s[w[id]] - val - s[id])) , val + s[id] , w[id]} , len - 1);
	else
		return Get({min(mn , f(s[l[id]] - val - p[id])) , val + p[id] , l[id]} , len - 1);
}

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	n = nn;
	s = ss;
	p = pp;
	w = ww;
	l = ll;
	s.push_back(0);
	p.push_back(0);
	w.push_back(n);
	l.push_back(n);
	for(int i = 0 ; i <= n ; i++)
	{
		a[i << 1][0] = {f(s[l[i]] - p[i]) , p[i] , l[i]};
		a[(i << 1) + 1][0] = {f(s[w[i]] - 2 * s[i]) , 2 * s[i] , w[i]};
	}
	for(int j = 1 ; j < Lg ; j++)  for(int i = 0 ; i <= 2 * n + 1 ; i++)
	{
		a[i][j] = Get(a[i][j - 1] , (1 << (j - 1)));
	}
}

long long simulate(int x, int z) {
	item tmp = Get({inf , z , x} , 2e7);
	return tmp.val;
}

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