oj.uz

Submission #429237

# Submission time Handle Problem Language Result Execution time Memory
429237 2021-06-15T19:21:30 Z amoo_safar Escape Route (JOI21_escape_route) C++17
100 / 100
 2165 ms 448564 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64972 KB Output is correct
2 Correct 37 ms 64964 KB Output is correct
3 Correct 82 ms 65092 KB Output is correct
4 Correct 37 ms 64992 KB Output is correct
5 Correct 39 ms 65048 KB Output is correct
6 Correct 32 ms 64940 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 134336 KB Output is correct
2 Correct 499 ms 151208 KB Output is correct
3 Correct 645 ms 142496 KB Output is correct
4 Correct 657 ms 150172 KB Output is correct
5 Correct 664 ms 150020 KB Output is correct
6 Correct 31 ms 64972 KB Output is correct
7 Correct 669 ms 139644 KB Output is correct
8 Correct 631 ms 142712 KB Output is correct
9 Correct 552 ms 128108 KB Output is correct
10 Correct 680 ms 149660 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64972 KB Output is correct
2 Correct 37 ms 64964 KB Output is correct
3 Correct 82 ms 65092 KB Output is correct
4 Correct 37 ms 64992 KB Output is correct
5 Correct 39 ms 65048 KB Output is correct
6 Correct 32 ms 64940 KB Output is correct
7 Correct 563 ms 134336 KB Output is correct
8 Correct 499 ms 151208 KB Output is correct
9 Correct 645 ms 142496 KB Output is correct
10 Correct 657 ms 150172 KB Output is correct
11 Correct 664 ms 150020 KB Output is correct
12 Correct 31 ms 64972 KB Output is correct
13 Correct 669 ms 139644 KB Output is correct
14 Correct 631 ms 142712 KB Output is correct
15 Correct 552 ms 128108 KB Output is correct
16 Correct 680 ms 149660 KB Output is correct
17 Correct 826 ms 136720 KB Output is correct
18 Correct 772 ms 135584 KB Output is correct
19 Correct 617 ms 150720 KB Output is correct
20 Correct 926 ms 140428 KB Output is correct
21 Correct 940 ms 151224 KB Output is correct
22 Correct 947 ms 151120 KB Output is correct
23 Correct 837 ms 139420 KB Output is correct
24 Correct 689 ms 143412 KB Output is correct
25 Correct 794 ms 125928 KB Output is correct
26 Correct 878 ms 149836 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64972 KB Output is correct
2 Correct 37 ms 64964 KB Output is correct
3 Correct 82 ms 65092 KB Output is correct
4 Correct 37 ms 64992 KB Output is correct
5 Correct 39 ms 65048 KB Output is correct
6 Correct 32 ms 64940 KB Output is correct
7 Correct 563 ms 134336 KB Output is correct
8 Correct 499 ms 151208 KB Output is correct
9 Correct 645 ms 142496 KB Output is correct
10 Correct 657 ms 150172 KB Output is correct
11 Correct 664 ms 150020 KB Output is correct
12 Correct 31 ms 64972 KB Output is correct
13 Correct 669 ms 139644 KB Output is correct
14 Correct 631 ms 142712 KB Output is correct
15 Correct 552 ms 128108 KB Output is correct
16 Correct 680 ms 149660 KB Output is correct
17 Correct 826 ms 136720 KB Output is correct
18 Correct 772 ms 135584 KB Output is correct
19 Correct 617 ms 150720 KB Output is correct
20 Correct 926 ms 140428 KB Output is correct
21 Correct 940 ms 151224 KB Output is correct
22 Correct 947 ms 151120 KB Output is correct
23 Correct 837 ms 139420 KB Output is correct
24 Correct 689 ms 143412 KB Output is correct
25 Correct 794 ms 125928 KB Output is correct
26 Correct 878 ms 149836 KB Output is correct
27 Correct 1097 ms 188904 KB Output is correct
28 Correct 1094 ms 191932 KB Output is correct
29 Correct 738 ms 208704 KB Output is correct
30 Correct 1163 ms 194168 KB Output is correct
31 Correct 1218 ms 205552 KB Output is correct
32 Correct 1185 ms 203096 KB Output is correct
33 Correct 739 ms 142240 KB Output is correct
34 Correct 1083 ms 179380 KB Output is correct
35 Correct 1222 ms 203044 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64972 KB Output is correct
2 Correct 37 ms 64964 KB Output is correct
3 Correct 82 ms 65092 KB Output is correct
4 Correct 37 ms 64992 KB Output is correct
5 Correct 39 ms 65048 KB Output is correct
6 Correct 32 ms 64940 KB Output is correct
7 Correct 563 ms 134336 KB Output is correct
8 Correct 499 ms 151208 KB Output is correct
9 Correct 645 ms 142496 KB Output is correct
10 Correct 657 ms 150172 KB Output is correct
11 Correct 664 ms 150020 KB Output is correct
12 Correct 31 ms 64972 KB Output is correct
13 Correct 669 ms 139644 KB Output is correct
14 Correct 631 ms 142712 KB Output is correct
15 Correct 552 ms 128108 KB Output is correct
16 Correct 680 ms 149660 KB Output is correct
17 Correct 826 ms 136720 KB Output is correct
18 Correct 772 ms 135584 KB Output is correct
19 Correct 617 ms 150720 KB Output is correct
20 Correct 926 ms 140428 KB Output is correct
21 Correct 940 ms 151224 KB Output is correct
22 Correct 947 ms 151120 KB Output is correct
23 Correct 837 ms 139420 KB Output is correct
24 Correct 689 ms 143412 KB Output is correct
25 Correct 794 ms 125928 KB Output is correct
26 Correct 878 ms 149836 KB Output is correct
27 Correct 1097 ms 188904 KB Output is correct
28 Correct 1094 ms 191932 KB Output is correct
29 Correct 738 ms 208704 KB Output is correct
30 Correct 1163 ms 194168 KB Output is correct
31 Correct 1218 ms 205552 KB Output is correct
32 Correct 1185 ms 203096 KB Output is correct
33 Correct 739 ms 142240 KB Output is correct
34 Correct 1083 ms 179380 KB Output is correct
35 Correct 1222 ms 203044 KB Output is correct
36 Correct 1823 ms 372672 KB Output is correct
37 Correct 1843 ms 411704 KB Output is correct
38 Correct 2103 ms 418952 KB Output is correct
39 Correct 2165 ms 448004 KB Output is correct
40 Correct 1980 ms 448564 KB Output is correct
41 Correct 900 ms 205140 KB Output is correct
42 Correct 2048 ms 402840 KB Output is correct
43 Correct 2033 ms 403748 KB Output is correct