제출 #1062704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1062704		aufan	던전 (IOI21_dungeons)	C++17	13 / 100	75 ms	26460 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

int n;
vector<int> s, p, w, l, dp;
vector<vector<pair<long long, int>>> bl;

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
	n = N; s = S; p = P; w = W; l = L;
	dp = vector<int>(n + 1, 0);
	bl = vector<vector<pair<long long, int>>>(n, vector<pair<long long, int>>(25));

	for (int i = n - 1; i >= 0; i--) dp[i] = dp[w[i]] + 1;
	
	for (int i = 0; i < n; i++) bl[i][0] = {p[i], l[i]};
	for (int j = 1; j < 25; j++) {
		for (int i = 0; i < n; i++) {
			auto [w, k] = bl[i][j - 1];
			if (k == n) {
				bl[i][j] = bl[i][j - 1];
			} else {
				auto [z, x] = bl[k][j - 1];
				bl[i][j] = {w + z, x};
			}
		}
	}

	return;
}

long long simulate(int x, int z) {
	long long f = z;
	for (int j = 24; j >= 0; j--) {
		if (x == n) break;
		
		if (f + bl[x][j].fi < s[0]) {
			f += bl[x][j].fi;
			x = bl[x][j].se;
		}
	}

	if (f < s[0] && x != n) {
		f += p[x];
		x = l[x];
	}

	f += 1ll * dp[x] * s[0];

	return f;
}

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