Submission #465355

#	Time	Username	Problem	Language	Result	Execution time	Memory
465355		Peti	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	5864 ms	2013696 KiB

dungeons

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

using namespace std;

const long long INF = (long long)1e18;
const int logn = 25, bont = 9, M = 3;

struct adat{
	int ind;
	long long legk, ossz;
	adat() {}
	adat(int ind, long long legk, long long ossz) : ind(ind), legk(legk), ossz(ossz) {}
};

inline adat merge(adat a, adat b){
	return adat(b.ind, min(a.legk, b.legk-a.ossz), a.ossz+b.ossz);
}

vector<vector<vector<adat>>> st;
vector<long long> ut;
vector<int> s, p, w, l;
int n;

void calcST(vector<vector<adat>> &v, int k){
	v.resize(n, vector<adat>(logn));
	for(int i = 0; i < n; i++){
		if(s[i] <= k)
			v[i][0] = adat(w[i], INF, s[i]);
		else
			v[i][0] = adat(l[i], s[i], p[i]);
	}
	for(int j = 1; j < logn; j++)
		for(int i = 0; i < n; i++)
			v[i][j] = merge(v[i][j-1], v[v[i][j-1].ind][j-1]);
}

void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	n = N;
	s = S;
	p = P;
	w = W;
	l = L;

	s.push_back(0);
	p.push_back(0);
	w.push_back(n);
	l.push_back(n);
	++n;

	st.resize(bont-1);
	for(int i = 0; i < bont-1; i++)
		calcST(st[i], 1<<(i*M));
	ut.resize(n, 0);
	for(int i = n-1; i >= 0; i--)
		ut[i] = ut[w[i]] + (long long)s[i];

	return;
}

long long simulate(int x, int z) {
	int y = 0;
	long long ert = z;
	while (x != n-1)
	{
		while (y+1 < bont && 1ll<<((y+1)*M) <= ert)
			++y;

		if(y+1 == bont){
			ert += ut[x];
			break;
		}

		for(int i = logn-1; i >= 0; i--){
			if(st[y][x][i].legk > ert){
				ert += st[y][x][i].ossz;
				x = st[y][x][i].ind;
			}
		}
		ert += (long long)s[x];
		x = w[x];
	}
	
	return ert;
}

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