Submission #1245371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245371		countless	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	7089 ms	8008 KiB

dungeons

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

typedef long long ll;
typedef long double ld;

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

int N;
vector<int> S, P, W, L;
vector<int> dep;
vector<vector<int>> adj;
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);

	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);
	return;
}

ll simulate(int x, int z) {
	ll at = x, ans = z;
	vector<bool> vis(N+1);
	vector<ll> mem(N+1);
	while (at != N) {
		// cerr << "i have" sp ans sp "at" sp at << ". i'm fighting against" sp S[at] << endl;
		if (ans >= S[at]) {
			return 1LL * dep[at] * S[at] + ans;
		} else {
			ans += P[at];
			at = L[at];

			if (vis[at]) {
				ll need = S[at] - ans;
				ll cyc = ans - mem[at];
				ll amt = need / cyc;

				// cerr << "cycle" sp cyc sp need sp amt << endl;

				ans += cyc * amt;
				// fill(vis.begin(), vis.end(), false);
			} else {
				vis[at] = true;
				mem[at] = ans;
			}
		}
		// cerr << "i'm now at" sp at sp "with" sp ans << endl;
		// cerr << endl;
	}

	return ans;
}

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