Submission #1049114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049114		parsadox2	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	7041 ms	404304 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)
{
	while(len != 0)
	{
		long long id = now.id , mn = now.mn , val = now.val , dif = val - (val >= s[id]) * s[id];
		bool flg = false;
		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];
			now = {min(mn , tmp.mn - dif) , tmp.val + dif , tmp.id};
			len = len - (1 << i);
			flg = true;
			break;
		}
		if(flg)
			continue;
		if(val >= s[id])
		{
			now = {min(mn , f(s[w[id]] - val - s[id])) , val + s[id] , w[id]};
			len--;
		}
		else
		{
			now = {min(mn , f(s[l[id]] - val - p[id])) , val + p[id] , l[id]};
			len--;
		}
	}
	return now;
}

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