Submission #634029

#	Time	Username	Problem	Language	Result	Execution time	Memory
634029		valerikk	Escape Route (JOI21_escape_route)	C++17	20 / 100	1854 ms	134736 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

std::vector<long long> calculate_necessary_time(
	int n, int m, long long S, int Q, std::vector<int> A, std::vector<int> B,
	std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
	std::vector<int> V, std::vector<long long> T) {

	for (int i = 0; i < m; ++i) {
		A.push_back(B[i]);
		B.push_back(A[i]);
		L.push_back(L[i]);
		C.push_back(C[i]);
	}
	m = A.size();

	vector<vector<int>> g(n);
	for (int i = 0; i < m; ++i) {
		g[A[i]].push_back(i);
	}

	auto dijkstra = [&](int s, ll t) {
		vector<ll> d(n, INF);
		d[s] = t;
		vector<bool> used(n, false);
		for (int it = 0; it < n; ++it) {
			int u = -1;
			for (int i = 0; i < n; ++i) {
				if (!used[i] && (u == -1 || d[i] < d[u])) {
					u = i;
				}
			}
			if (d[u] == INF) break;
			used[u] = true;
			for (int e : g[u]) {
				int v = B[e];
				ll cur = d[u] + L[e];
				if (cur > C[e]) cur += S - d[u] % S;
				d[v] = min(d[v], cur);
			}
		}
		return d;
	};

	vector<vector<ll>> dist0(n);
	for (int i = 0; i < n; ++i) {
		dist0[i] = dijkstra(i, 0);
	}
	vector<vector<ll>> dist_edge(m);
	for (int i = 0; i < m; ++i) {
		dist_edge[i] = dijkstra(A[i], C[i] - L[i]);
		for (int v = 0; v < n; ++v) {
			if (dist_edge[i][v] <= S) {
				dist_edge[i][v] -= C[i] - L[i];
			} else {
				dist_edge[i][v] = INF;
			}
		}
	}

	vector<ll> ans(Q);
	for (int i = 0; i < Q; ++i) {
		ans[i] = (S - T[i]) % S + dist0[U[i]][V[i]];
	}

	for (int i = 0; i < n; ++i) {
		sort(g[i].begin(), g[i].end(), [&](int ei, int ej) {
			return C[ei] - L[ei] > C[ej] - L[ej];
		});
	}

	for (int s = 0; s < n; ++s) {
		vector<int> queries;
		for (int i = 0; i < Q; ++i) {
			if (U[i] == s) {
				queries.push_back(i);
			}
		}
		sort(queries.begin(), queries.end(), [&](int i, int j) {
			return T[i] > T[j];
		});
		int qind = 0;
		vector<int> ind(n, 0);
		vector<ll> d(n, INF);
		d[s] = 0;
		long long mn = INF;
		while (true) {
			pair<ll, int> mx = {-1, -1};
			for (int u = 0; u < n; ++u) {
				if (ind[u] < (int)g[u].size()) {
					int e = g[u][ind[u]];
					mx = max(mx, {C[e] - L[e] - d[u], u});
				}
			}
			while (qind < (int)queries.size() && T[queries[qind]] > mx.first) {
				int i = queries[qind++];
				ans[i] = min(ans[i], d[V[i]]);
				for (int u = 0; u < n; ++u) {
					if (d[u] < INF) {
						ans[i] = min(ans[i], S - T[i] + dist0[u][V[i]]);
					}
				}
			}
			if (mx.first < 0) break;
			int e = g[mx.second][ind[mx.second]++];
			if (mx.first <= mn) {
				for (int i = 0; i < n; ++i) {
					if (dist_edge[e][i] < INF) {
						d[i] = min(d[i], dist_edge[e][i] + d[mx.second]);
					}
				}
			}
			mn = min(mn, mx.first);
		}
	}
	return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30