제출 #1019401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1019401		aykhn	던전 (IOI21_dungeons)	C++17	89 / 100	3729 ms	2097152 KiB

dungeons

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

using namespace std;

#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 4e5 + 5;
const int LOG = 24;
const int LG = 9;

int N;
long long p[LOG][LG][MXN], mn[LOG][LG][MXN], gain[LOG][LG][MXN];

struct Tree
{
	int id;
	void init()
	{
		for (int lg = 1; lg < LG; lg++)
		{
			for (int i = 0; i <= N; i++)
			{
				mn[id][lg][i] = mn[id][lg - 1][i];
				gain[id][lg][i] = gain[id][lg - 1][i];
				p[id][lg][i] = p[id][lg - 1][i];
				for (int j = 1; j < 6; j++)
				{
					mn[id][lg][i] = min(mn[id][lg][i], mn[id][lg - 1][p[id][lg][i]] - gain[id][lg][i]);
					gain[id][lg][i] = gain[id][lg][i] + gain[id][lg - 1][p[id][lg][i]];
					p[id][lg][i] = p[id][lg - 1][p[id][lg][i]];
				}
			}
		}
	}
	void move(int &x, long long &val)
	{
		if (x == N) return;
		for (int i = LG - 1; i >= 0; i--)
		{
			for (int j = 0; j < 6; j++)
			{
				if (val < mn[id][i][x])
				{
					val += gain[id][i][x];
					x = p[id][i][x];
				}
				else break;
			}
		}
	}
};

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

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

long long simulate(int x, int z) 
{
	long long val = z;
	int cnt = 0;
	while (x != N)
	{
		cnt++;
		assert(cnt < 2000);
		int lg = 0;
		long long tmp = val;
		while (tmp > 1) lg++, tmp >>= 1;
		lg = min(lg, LOG - 1);
		t[lg].move(x, val);
		if (x == N) break;
		val += S[x];
		x = W[x];
	}
	return 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