Submission #1019384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019384		aykhn	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	698 ms	1209304 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 5e4 + 5;
const int LOG = 24;

int N;

struct Tree
{
	vector<long long> p[LOG], mn[LOG], gain[LOG];
	void givesz()
	{
		for (int i = 0; i < LOG; i++) p[i].assign(N + 1, 0), mn[i].assign(N + 1, 0), gain[i].assign(N + 1, 0);
	}
	void init()
	{
		for (int lg = 1; lg < LOG; lg++)
		{
			for (int i = 0; i <= N; i++)
			{
				mn[lg][i] = min(mn[lg - 1][i], mn[lg - 1][p[lg - 1][i]] - gain[lg - 1][i]);
				gain[lg][i] = gain[lg - 1][i] + gain[lg - 1][p[lg - 1][i]];
				p[lg][i] = p[lg - 1][p[lg - 1][i]];
			}
		}
	}
	void move(int &x, long long &val)
	{
		if (x == N) return;
		for (int i = LOG - 1; i >= 0; i--)
		{
			if (val < mn[i][x])
			{
				val += gain[i][x];
				x = p[i][x];
			}
		}
	}
};

Tree t[LOG];
vector<long long> S, P, W, L;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) 
{
	N = n;
	for (int &i : s) S.push_back(i);
	for (int &i : p) P.push_back(i);
	for (int &i : w) W.push_back(i);
	for (int &i : l) L.push_back(i);
	for (int i = 0; i < LOG; i++)
	{
		t[i].givesz();
		for (int j = 0; j < N; j++)
		{
			if (s[j] < (1LL << i))
			{
				t[i].p[0][j] = w[j];
				t[i].gain[0][j] = s[j];
				t[i].mn[0][j] = inf;
			}
			else
			{
				t[i].p[0][j] = l[j];
				t[i].gain[0][j] = p[j];
				t[i].mn[0][j] = s[j];
			}
		}
		t[i].p[0][N] = N, t[i].gain[0][N] = 0, t[i].mn[0][N] = inf;
		t[i].init();
	}
}

long long simulate(int x, int z) 
{
	long long val = z;
	while (x != N)
	{
		int lg = 0;
		long long tmp = val;
		while (tmp > 1) lg++, tmp >>= 1;
		t[lg].move(x, val);
		if (x == N) break;
		val += S[x];
		x = W[x];
	}
	return val;
}

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