제출 #625043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625043		SuhaibSawalha1	던전 (IOI21_dungeons)	C++17	0 / 100	1 ms	596 KiB

dungeons

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

vector<int> s, p, w, l, dis;
vector<vector<int>> anc;
vector<vector<long long>> sum;
int n;
void dfs (int u) {
	if (u == n || dis[u]) {
		return;
	}
	dfs(w[u]);
	dis[u] = dis[w[u]] + 1;
}
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;
	dis.assign(n + 1, 0);
	anc.assign(20, vector<int>(n + 1, -1));
	sum.assign(20, vector<long long>(n + 1, 0));
	for (int i = 0; i < n; ++i) {
		dfs(i);
		anc[0][i] = l[i];
		sum[0][i] = p[i];
	}
	for (int i = 1; i < 20; ++i) {
		for (int j = 0; j <= n; ++j) {
			if (~anc[i - 1][j]) {
				anc[i][j] = anc[i - 1][anc[i - 1][j]];
				sum[i][j] += sum[i - 1][anc[i - 1][j]];
			}
		}
	}
	return;
}

long long simulate(int x, int z) {
	long long ans = z;
	for (int i = 19; ~i && x < n; --i) {
		if (ans + sum[i][x] < s[0]) {
			ans += sum[i][x];
			x = anc[i][x];
		}
	}
	return ans + (long long)dis[x] * s[0];
}

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