Submission #1316181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316181		vlomaczk	Escape Route (JOI21_escape_route)	C++20	0 / 100	604 ms	112012 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

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) {
	vector<ll> K(M);
	for(ll i=0; i<M; ++i) K[i] = C[i] - L[i];
	vector<ll> ans(Q);
	vector<vector<vector<ll>>> queries(N, vector<vector<ll>>(N));
	for(ll i=0; i<Q; ++i) {
		queries[U[i]][V[i]].push_back(i);
	} 
	vector<vector<pair<ll, ll>>> g(N);
	for(ll i=0; i<M; ++i) {
		g[A[i]].push_back({B[i], i});
		g[B[i]].push_back({A[i], i});
	}
	ll inf = 1e18;
	auto dijkstra_min = [&](ll s, ll val) {
		vector<ll> dist(N, inf), vis(N,0);
		dist[s] = val;
		while(1) {
			pair<ll, ll> best = {inf,0};
			for(ll i=0; i<N; ++i) if(!vis[i]) best = min(best, {dist[i], i});
			if(best.first == inf) break;
			auto[dv,v] = best;
			vis[v] = 1;
			for(auto[u,k] : g[v]) {
				ll w = L[k];
				ll t = dv%S;
				if(t > K[k]) w += S-t;
				if(dist[u] > dist[v] + w) {
					dist[u] = dist[v] + w;
				}
			}
		}
		return dist;
	};
	auto dijkstra_max = [&](ll s, ll val) {
		vector<ll> dist(N, -1), vis(N,0);
		dist[s] = val;
		while(1) {
			pair<ll, ll> best = {-1,0};
			for(ll i=0; i<N; ++i) if(!vis[i]) best = max(best, {dist[i], i});
			if(best.first == -1) break;
			auto[dv,v] = best;
			vis[v] = 1;
			for(auto[u,k] : g[v]) {
				ll nd = min(K[k], dv-L[k]);
				if(dist[u] < nd) {
					dist[u] = nd;
				}
			}
		}
		return dist;
	}; 
	vector<vector<ll>> day0(N);
	for(ll i=0; i<N; ++i) day0[i] = dijkstra_max(i, S-1);
	vector<vector<ll>> dist(N);
	for(ll i=0; i<N; ++i) dist[i] = dijkstra_min(i, 0);
	vector<vector<ll>> DX(2*M), DY(2*M);
	for(int i=0; i<M; ++i) {
		DX[2*i] = dijkstra_max(A[i], K[i]);
		DX[2*i+1] = dijkstra_max(B[i], K[i]);
		DY[2*i] = dijkstra_min(B[i], C[i]);
		DY[2*i+1] = dijkstra_min(A[i], C[i]);
	}
	vector<int> edges;
	for(int i=0; i<2*M; ++i) edges.push_back(i);
	for(ll s=0; s<N; ++s) {
		sort(edges.begin(), edges.end(), [&](int i, int j) {
			return DX[i][s] > DX[j][s];
		});
		for(ll u=0; u<N; ++u) {
			sort(queries[s][u].begin(), queries[s][u].end(), [&](int i, int j) { return T[i] > T[j]; });
			ll best = inf;
			int cnt = 0;
			for(auto idx : queries[s][u]) {
				while(cnt < edges.size()) {
					int i = edges[cnt];
					if(DX[i][s] >= T[idx]) {
						best = min(best, DY[i][u] - DX[i][s]);
						cnt++;
					} else break;
				}
				if(T[idx]==0) {
					ans[idx] = dist[s][u];
					continue;
				}
				ans[idx] = inf;
				if(day0[u][s] < T[idx]) {
					for(int i=0; i<N; ++i) if(day0[i][s] >= T[idx]) ans[idx] = min(ans[idx], S + dist[i][u]);
					ans[idx] -= T[idx];
				} else {
					// cout << idx << ": " << s << " -> " << u << " " << T[idx] << "\n";
					ans[idx] = best;
				}
			}
		}
	}
	return ans;
}

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