제출 #1195986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195986		belgianbot	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	46 ms	21936 KiB

dungeons

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

const int MAX_N = 50001;
const int LOG = 20;
vector<long long> win(MAX_N);
vector<vector<pair<long long, int>>> vec(MAX_N, vector<pair<long long,int>>(LOG));
vector<int> s,p,w,l, toCycle(MAX_N);
int n;

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	s = ss; p = pp; w = ww; l = ll; n = nn;
	l.push_back(n); p.push_back(0);
	for (int i = 0; i <= n; i++) {
		vec[i][0] = {(long long)(p[i]), l[i]};
	}
	for (int i = 1; i < LOG; i++) {
		for (int j = 0; j <= n; j++) {
			vec[j][i] = {vec[vec[j][i-1].second][i-1].first + vec[j][i-1].first, vec[vec[j][i-1].second][i-1].second};
		}
	}
	win[n] = 0;
	for (int i = n-1; i >= 0; i--) {
		win[i] = win[w[i]] + s[i];
	}
	return;
}

long long simulate(int x, int z) {
	long long res = LLONG_MAX;
	long long lim = s[x];
	long long st = z;
	int pos = x;
	if (st >= lim) return st+ win[pos];
	
	for (int i = LOG-1; i >= 0; i--) {
		if (st + vec[pos][i].first >= lim) res = st + vec[pos][i].first + win[vec[pos][i].second];
		else {
			st += vec[pos][i].first;
			pos = vec[pos][i].second;
		}
	}
	if (st + vec[pos][0].first >= lim) return st +vec[pos][0].first + win[vec[pos][0].second];
	return res;
}

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