제출 #446850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446850		prvocislo	던전 (IOI21_dungeons)	C++17	100 / 100	3882 ms	1566672 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxd1 = 8, maxd2 = 24, maxn = 4e5 + 5, base = 8;
const ll inf = 1e18 + 5ll;
vector<pair<int, int> > g[maxn];
int kam[maxd1][maxd2][maxn], pw[maxd1+1], n;
vector<int> s, p, w, l;
ll sum[maxd1][maxd2][maxn], mini[maxd1][maxd2][maxn], onlywin[maxn];
void dfs(int u, ll w)
{
	onlywin[u] = w;
	for (pair<int, int> i : g[u]) dfs(i.first, w+i.second);
}
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) 
{
	s.push_back(0), p.push_back(0), w.push_back(n), l.push_back(n);
	::n = n, ::s = s, ::p = p, ::w = w, ::l = l;
	pw[0] = 1;
	for (int i = 1; i <= maxd1; i++) pw[i] = pw[i-1] * base;
	for (int i = 0; i < maxd1; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			if (s[j] <= pw[i]) 
			{
				sum[i][0][j] = s[j], kam[i][0][j] = w[j];
				mini[i][0][j] = inf;
			}
			else 
			{
				sum[i][0][j] = p[j], kam[i][0][j] = l[j];
				mini[i][0][j] = s[j];
			}
		}
		for (int j = 1; j < maxd2; j++) for (int k = 0; k < maxn; k++)
		{
			kam[i][j][k] = kam[i][j-1][kam[i][j-1][k]];
			sum[i][j][k] = sum[i][j-1][k] + sum[i][j-1][kam[i][j-1][k]];
			mini[i][j][k] = min(mini[i][j-1][k], mini[i][j-1][kam[i][j-1][k]] - sum[i][j-1][k]);
		}
	}
	for (int i = 0; i < n; i++) g[w[i]].push_back({i, s[i]});
	dfs(n, 0);
}
ll simulate(int x, int z) 
{
	ll st = z;
	for (int i = 0; i < maxd1; i++)
	{
		while (x != n && st < pw[i+1])
		{
			for (int j = maxd2-1; j >= 0; j--) if (mini[i][j][x] > st)
			{
				st += sum[i][j][x];
				x = kam[i][j][x];
			}
			st += s[x];
			x = w[x];
		}	
	}
	return st + onlywin[x];
}

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