제출 #1245455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245455		countless	던전 (IOI21_dungeons)	C++20	0 / 100	7090 ms	23540 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, end, par;
vector<ll> trav, dep;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> up;
vector<vector<ll>> sum;

int find(int u) {
	if (u == par[u]) return u;
	return par[u] = find(par[u]);
}

void unite(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	if (dep[u] > dep[v]) swap(u, v);
	par[v] = u;
}

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;
	trav.resize(N+1), adj.resize(N+1), dep.resize(N+1), par.resize(N+1);
	up.assign(LOGN, vector<int>(N+1));
	sum.assign(LOGN, vector<ll>(N+1));
	iota(par.begin(), par.end(), 0);

	using edge = tuple<ll, int, int>;
	vector<edge> edges;
	for (int i = 0; i < N; i++) {
		adj[W[i]].emplace_back(i, S[i]);
		edges.emplace_back(S[i], i, W[i]);
	}
	sort(edges.begin(), edges.end());

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

	pre(pre, N, -1);

	vector<bool> proc(N+1);
	int lo = 0, hi = 0;
	while (lo < N) {
		hi = lo;
		while (hi < N and get<0>(edges[lo]) == get<0>(edges[hi])) hi++;

		for (int i = lo; i < hi; i++) {
			auto [w, u, v] = edges[i];
			if (proc[u] or proc[v] or u == N or v == N) continue;
			unite(u, v);
		}

		for (int i = lo; i < hi; i++) {
			auto [w, u, v] = edges[i];
			proc[u] = proc[v] = true;
		}

		lo = hi;
	}

	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;

	cerr << endl << endl << endl;
	while (true) {
		for (int j = LOGN-1; j >= 0; j--) {
			// cerr << at sp ans sp sum[j][at] sp S[find(at)] << endl;
			if (up[j][at] != N and ans + sum[j][at] < S[find(at)]) {
				ans += sum[j][at];
				at = up[j][at];
			}
		}

		// cerr << at sp ans << endl;
		if (up[0][at] == N or ans < S[find(at)]) {
			ans += sum[0][at];
			at = up[0][at];
		}
		
		if (at == N) return trav[at] + ans;
		if (ans >= S[find(at)]) {
			ans += S[at];
			at = W[at];
		}
	}

	return trav[at] + 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