Submission #429237

#	Time	Username	Problem	Language	Result	Execution time	Memory
429237		amoo_safar	Escape Route (JOI21_escape_route)	C++17	100 / 100	2165 ms	448564 KiB

escape_route

#include "escape_route.h"

#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr <<  #x << " : " << x << '\n';

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;

const int N = 92;
const ll Inf = 1e18;

int n, m;
ll S;

vi A, B;
vl L, C;
vector<int> G[N];

ll dj_dis[N], dj_mk[N];

void Djik(int src, ll st){
	memset(dj_dis, 31, sizeof dj_dis);
	memset(dj_mk, 0, sizeof dj_mk);
	dj_dis[src] = st;
	int adj;
	ll w;
	for(int _ = 0; _ < n; _++){
		int idx = -1;
		for(int i = 0; i < n; i++) if(!dj_mk[i]) idx = i;
		if(idx == -1) continue;
		for(int i = 0; i < n; i++) if(!dj_mk[i] && dj_dis[i] < dj_dis[idx]) idx = i;
		dj_mk[idx] = 1;
		for(auto e : G[idx]){
			adj = A[e] ^ B[e] ^ idx;
			if(dj_dis[idx] % S <= C[e] - L[e])
				w = dj_dis[idx] + L[e];
			else 
				w = dj_dis[idx] + (S - (dj_dis[idx] % S)) + L[e];
			if(w < dj_dis[adj])
				dj_dis[adj] = w;
		}
	}
}
ll dis0[N][N];

ll dis[N][N * N][N]; // u. no of (good) act. adj
ll tim[N][N * N], po[N];  //u. no of act.
int mk[N][N * N]; // u id_e

int Get(int u, ll st){
	int L = -1, R = po[u] + 1, mid;
	while(L + 1 < R){
		mid = (L + R) >> 1;
		if(tim[u][mid] >= st) L = mid;
		else R = mid;
	}
	assert(L != -1);
	return L;
}

int poi[N][N];


pll Calc(int u){
	ll mn = S + 1;
	int idx = -1;
	for(int v = 0; v < n; v++){
		if(dis[u][ po[u] ][v] > S) continue;
		for(int &i = poi[u][v]; i < (int) G[v].size(); i++){
			int e = G[v][i];
			if(mk[u][e]) continue;
			ll wt = dis[u][ po[u] ][v] - (C[e] - L[e]);
			wt = max(wt, 0ll);
			if(wt < mn){
				mn = wt;
				idx = e;
			}
			break;
		}
	}
	return pll(idx == -1 ? S + 1 : tim[u][po[u]] - mn, idx);
}

ll nw_dis[N];

set< pair<pll, int> > cand;

bool Step(){
	if(cand.empty()) return false;
	pair<pll, int> bst = *cand.rbegin(); //{pll(-1, -1), -1};
	cand.erase(bst);
	if(bst.F.S == -1) return true;
	// for(int i = 0; i < n; i++){
	// 	auto res = Calc(i);
	// 	if(res.S == -1) continue;
	// 	bst = max(bst, {Calc(i), i});
	// }
	// if(bst.S == -1) return false;

	int u = bst.S;
	int ed = bst.F.S;
	ll del = tim[u][po[u]] - bst.F.F;
	mk[u][ed] = 1;
	// if(u == 0){
	// 	cerr << "&& " << A[ed] << ' ' << B[ed] << '\n';
	// }
	if(tim[u][ po[u] ] < del){
		cand.insert({Calc(u), u});
		return true;
	}
	// cerr << "******* " << u << ' ' << tim[u][po[u]] - del << ' ' << bst.S << '\n';
	fill(nw_dis, nw_dis + N, S + 1);
	// old
	for(int i = 0; i < n; i++)
		if(dis[u][po[u]][i] != S + 1)
			nw_dis[i] = min(nw_dis[i], dis[u][ po[u] ][i] - del);

	int fr = A[ed], to = B[ed];
	if(nw_dis[fr] > nw_dis[to]) swap(fr, to);
	
	int lay = Get(to, C[ed]);
	// if(u == 0 && (ed == 0 || ed == 2)){
	// 	debug(to);
	// 	debug(dis[to][lay][to]);
	// 	debug(C[ed]);
	// 	debug(tim[to][lay]);
	// }
	for(int i = 0; i < n; i++)
		if(dis[to][lay][i] <= S)
			nw_dis[i] = min(nw_dis[i], dis[to][lay][i] - (tim[to][lay] - C[ed]));
	
	po[u] ++;
	tim[u][po[u]] = tim[u][po[u] - 1] - del;

	for(int i = 0; i < n; i++)
		dis[u][po[u]][i] = nw_dis[i];

	cand.insert({Calc(u), u});
	return true;
}

vl calculate_necessary_time(int _n, int _m, ll _S, int Q, vi _A, vi _B, vl _L, vl _C, vi _U, vi _V, vl _T) {
	n = _n; m = _m; S = _S;
	A = _A; B = _B; L = _L; C = _C;
	for(int i = 0; i < m; i++)
		G[A[i]].pb(i), G[B[i]].pb(i);
	for(int i = 0; i < n; i++)
		sort(all(G[i]), [&](int e1, int e2){
			return C[e1] - L[e1] > C[e2] - L[e2];
		});
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			fill(dis[i][j], dis[i][j] + n, S + 1);
	for(int i = 0; i < n; i++){
		po[i] = 0;
		tim[i][0] = S;
		dis[i][0][i] = S;
	}
	for(int i = 0; i < n; i++)
		cand.insert({Calc(i), i});
	while(Step()) ;
	for(int i = 0; i < n; i++){
		Djik(i, 0);
		for(int j = 0; j < n; j++)
			dis0[i][j] = dj_dis[j];
	}

	vl ANS;
	// for(int i = 0; i <= po[0]; i++){
	// 	cerr << "lay : " << tim[0][i] << '\n';
	// 	cerr << "! ";
	// 	for(int j = 0; j < n; j++)
	// 		cerr << dis[0][i][j] << ' ';
	// 	cerr << '\n';
	// }
	for(int i = 0; i < Q; i++){
		int lay = Get(_U[i], _T[i]);
		// if(i == 0){
		// 	debug(tim[_U[i]][lay]);
		// 	debug(dis[_U[i]][lay][_V[i]]);
		// 	// Djik(_U[i], _T[i]);
		// 	debug(tim[_U[i]][lay] - _T[i]);
		// }
		if(dis[_U[i]][lay][_V[i]] <= S)
			ANS.pb((dis[_U[i]][lay][_V[i]] - (tim[_U[i]][lay] - _T[i])) - _T[i]);
		else {
			ll res = Inf;
			for(int j = 0; j < n; j++){
				if(dis[_U[i]][lay][j] <= S){
					res = min(res, S - _T[i] + dis0[j][_V[i]]);
				}
			}
			ANS.pb(res);
		}
		// ANS.pb(dis[_V[i]] - _T[i]);
	}
	return ANS;
}

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