Submission #1245415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245415		countless	Dungeons Game (IOI21_dungeons)	C++20	13 / 100	60 ms	22776 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

const int MAXN = 4e5+5;
const int LOGN = 25;

int N;
vector<int> S, P, W, L, dep;
vector<vector<int>> adj, up;
vector<vector<ll>> sum;
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;
	dep.resize(N+1), adj.resize(N+1);
	up.assign(LOGN, vector<int>(N+1));
	sum.assign(LOGN, vector<ll>(N+1));

	for (int i = 0; i < N; i++) {
		adj[W[i]].push_back(i);
	}

	auto dfs = [&](auto &&dfs, int u, int p) -> void {
		for (auto &v : adj[u]) {
			if (v != p) {
				dep[v] = dep[u] + 1;
				dfs(dfs, v, u);
			}
		}
	};

	dfs(dfs, N, -1);

	for (int i = 0; i <= N; i++) {
		up[0][i] = (i != N ? L[i] : N);
		sum[0][i] = (i != N ? P[i] : 0);
	}

	for (int j = 1; j < LOGN; j++) {
		for (int i = 0; i <= N; i++) {
			up[j][i] = up[j-1][ up[j-1][i] ];
			sum[j][i] = sum[j-1][i] + sum[j-1][ up[j-1][i] ];
		}
	}

	return;
}

ll simulate(int x, int z) {
	ll at = x, ans = z;

	for (int j = LOGN-1; j >= 0; j--) {
		if (up[j][at] != N and ans + sum[j][at] < S[at]) {
			ans += sum[j][at];
			at = up[j][at];
		}
	}

	if (ans >= S[at]) return 1LL * dep[at] * S[at] + ans;
	ans += sum[0][at];
	at = up[0][at];
	if (!(ans >= S[at] or at == N)) {
		cerr << x sp z sp ans sp S[at] sp at sp N << endl;
	}
	assert(ans >= S[at] or at == N);
	return 1LL * dep[at] * S[at] + ans;
}

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