제출 #1210098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210098		siewjh	Escape Route (JOI21_escape_route)	C++20	100 / 100	1475 ms	204600 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 91;
const int MAXM = 4010;
const ll inf = 4e18;
vector<pair<int, int>> adj[MAXN];
bool vis[MAXN];
vector<pair<ll, int>> qv[MAXN][MAXN];
ll rdist[MAXM][2][MAXN], fdist[MAXM][2][MAXN], mtsd[MAXN][MAXN], d0[MAXN][MAXN];

vector<ll> calculate_necessary_time(
int N, int M, ll S, int Q,
vector<int> A, vector<int> B, vector<ll> L, vector<ll> C,
vector<int> U, vector<int> V, vector<ll> T){
	for (int i = 0; i < M; i++){
		int a = A[i], b = B[i];
		adj[a].push_back({b, i}); adj[b].push_back({a, i});
	}
	for (int i = 0; i < M; i++)
		for (int k = 0; k < 2; k++)
			for (int x = 0; x < N; x++){
				rdist[i][k][x] = -1; fdist[i][k][x] = inf;
			}
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++){
			mtsd[i][j] = -1; d0[i][j] = inf;
		}
	for (int i = 0; i < M; i++){
		int a = A[i], b = B[i]; ll l = L[i], c = C[i];
		for (int k = 0; k < 2; k++){
			memset(vis, 0, sizeof(vis));
			rdist[i][k][a] = c - l;
			while (1){
				int cx = -1; ll cv = -1;
				for (int x = 0; x < N; x++)
					if (!vis[x] && rdist[i][k][x] > cv){
						cx = x; cv = rdist[i][k][x];
					}
				if (cx == -1) break;
				vis[cx] = 1;
				for (auto [nn, ne] : adj[cx]){
					if (vis[nn]) continue;
					ll nd = min(C[ne], cv) - L[ne];
					if (nd > rdist[i][k][nn]) rdist[i][k][nn] = nd;
				}
			}
			memset(vis, 0, sizeof(vis));
			fdist[i][k][b] = c;
			while (1){
				int cx = -1; ll cv = inf;
				for (int x = 0; x < N; x++)
					if (!vis[x] && fdist[i][k][x] < cv){
						cx = x; cv = fdist[i][k][x];
					}
				if (cx == -1) break;
				vis[cx] = 1;
				for (auto [nn, ne] : adj[cx]){
					if (vis[nn]) continue;
					ll nd = cv + L[ne];
					if (nd < min(C[ne] + 1, fdist[i][k][nn])) fdist[i][k][nn] = nd;
				}
			}
			swap(a, b);
		}
	}			
	for (int i = 0; i < N; i++){
		memset(vis, 0, sizeof(vis));
		mtsd[i][i] = S - 1;
		while (1){
			int cx = -1; ll cv = -1;
			for (int x = 0; x < N; x++)
				if (!vis[x] && mtsd[i][x] > cv){
					cx = x; cv = mtsd[i][x];
				}
			if (cx == -1) break;
			vis[cx] = 1;
			for (auto [nn, ne] : adj[cx]){
				if (vis[nn]) continue;
				ll nd = min(C[ne], cv) - L[ne];
				if (nd > mtsd[i][nn]) mtsd[i][nn] = nd;
			}
		}
		memset(vis, 0, sizeof(vis));
		d0[i][i] = 0;
		while (1){
			int cx = -1; ll cv = inf;
			for (int x = 0; x < N; x++)
				if (!vis[x] && d0[i][x] < cv){
					cx = x; cv = d0[i][x];
				}
			if (cx == -1) break;
			vis[cx] = 1;
			ll ct = cv % S, ndy = cv - ct + S;
			for (auto [nn, ne] : adj[cx]){
				if (vis[nn]) continue;
				ll nd = (ct <= C[ne] - L[ne] ? cv : ndy) + L[ne];
				if (nd < d0[i][nn]) d0[i][nn] = nd;
			}
		}
	}
	for (int i = 0; i < Q; i++) qv[U[i]][V[i]].push_back({T[i], i});
	vector<ll> av(Q);
	for (int u = 0; u < N; u++){
		vector<tuple<ll, int, int>> eord;
		for (int i = 0; i < M; i++)
			for (int k = 0; k < 2; k++)
				if (rdist[i][k][u] != -1)
					eord.push_back({rdist[i][k][u], i, k});
		sort(eord.begin(), eord.end());
		vector<pair<ll, int>> rbde;
		for (int i = 0; i < N; i++)
			if (mtsd[u][i] != inf)
				rbde.push_back({mtsd[i][u], i});
		sort(rbde.begin(), rbde.end());
		for (int v = 0; v < N; v++){
			sort(qv[u][v].begin(), qv[u][v].end(), greater<pair<ll, int>>());
			int eid = eord.size() - 1, did = rbde.size() - 1;
			ll ans = inf, ansd = inf;
			for (auto [tm, id] : qv[u][v]){
				for (; eid >= 0 && get<0>(eord[eid]) >= tm; eid--){
					ll st; int i, k; tie(st, i, k) = eord[eid];
					ans = min(ans, fdist[i][k][v] - st);
				}
				for (; did >= 0 && rbde[did].first >= tm; did--){
					ll st; int x; tie(st, x) = rbde[did];
					ansd = min(ansd, d0[x][v]);
				}
				av[id] = min(ans, S - tm + ansd);
			}
		}
	}
	return av;
}

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