oj.uz

Submission #429223

# Submission time Handle Problem Language Result Execution time Memory
429223 2021-06-15T19:11:17 Z amoo_safar Escape Route (JOI21_escape_route) C++17
70 / 100
 3229 ms 237860 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 = 62;
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;
}

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(auto e : G[v]){
			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;
			}
		}
	}
	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++)
		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 33 ms 65008 KB Output is correct
2 Correct 44 ms 64972 KB Output is correct
3 Correct 234 ms 65052 KB Output is correct
4 Correct 30 ms 64992 KB Output is correct
5 Correct 155 ms 64992 KB Output is correct
6 Correct 32 ms 65040 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 123460 KB Output is correct
2 Correct 655 ms 151568 KB Output is correct
3 Correct 776 ms 139680 KB Output is correct
4 Correct 807 ms 155472 KB Output is correct
5 Correct 804 ms 155512 KB Output is correct
6 Correct 30 ms 64972 KB Output is correct
7 Correct 811 ms 138636 KB Output is correct
8 Correct 585 ms 153712 KB Output is correct
9 Correct 722 ms 126904 KB Output is correct
10 Correct 817 ms 154888 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65008 KB Output is correct
2 Correct 44 ms 64972 KB Output is correct
3 Correct 234 ms 65052 KB Output is correct
4 Correct 30 ms 64992 KB Output is correct
5 Correct 155 ms 64992 KB Output is correct
6 Correct 32 ms 65040 KB Output is correct
7 Correct 777 ms 123460 KB Output is correct
8 Correct 655 ms 151568 KB Output is correct
9 Correct 776 ms 139680 KB Output is correct
10 Correct 807 ms 155472 KB Output is correct
11 Correct 804 ms 155512 KB Output is correct
12 Correct 30 ms 64972 KB Output is correct
13 Correct 811 ms 138636 KB Output is correct
14 Correct 585 ms 153712 KB Output is correct
15 Correct 722 ms 126904 KB Output is correct
16 Correct 817 ms 154888 KB Output is correct
17 Correct 964 ms 136628 KB Output is correct
18 Correct 943 ms 135376 KB Output is correct
19 Correct 762 ms 151840 KB Output is correct
20 Correct 1077 ms 137556 KB Output is correct
21 Correct 1063 ms 151216 KB Output is correct
22 Correct 1044 ms 149888 KB Output is correct
23 Correct 1046 ms 133264 KB Output is correct
24 Correct 764 ms 146548 KB Output is correct
25 Correct 955 ms 118488 KB Output is correct
26 Correct 1099 ms 142452 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65008 KB Output is correct
2 Correct 44 ms 64972 KB Output is correct
3 Correct 234 ms 65052 KB Output is correct
4 Correct 30 ms 64992 KB Output is correct
5 Correct 155 ms 64992 KB Output is correct
6 Correct 32 ms 65040 KB Output is correct
7 Correct 777 ms 123460 KB Output is correct
8 Correct 655 ms 151568 KB Output is correct
9 Correct 776 ms 139680 KB Output is correct
10 Correct 807 ms 155472 KB Output is correct
11 Correct 804 ms 155512 KB Output is correct
12 Correct 30 ms 64972 KB Output is correct
13 Correct 811 ms 138636 KB Output is correct
14 Correct 585 ms 153712 KB Output is correct
15 Correct 722 ms 126904 KB Output is correct
16 Correct 817 ms 154888 KB Output is correct
17 Correct 964 ms 136628 KB Output is correct
18 Correct 943 ms 135376 KB Output is correct
19 Correct 762 ms 151840 KB Output is correct
20 Correct 1077 ms 137556 KB Output is correct
21 Correct 1063 ms 151216 KB Output is correct
22 Correct 1044 ms 149888 KB Output is correct
23 Correct 1046 ms 133264 KB Output is correct
24 Correct 764 ms 146548 KB Output is correct
25 Correct 955 ms 118488 KB Output is correct
26 Correct 1099 ms 142452 KB Output is correct
27 Correct 2653 ms 161564 KB Output is correct
28 Correct 2569 ms 204320 KB Output is correct
29 Correct 2193 ms 228332 KB Output is correct
30 Correct 2762 ms 208324 KB Output is correct
31 Correct 2776 ms 237860 KB Output is correct
32 Correct 2654 ms 237836 KB Output is correct
33 Correct 815 ms 199960 KB Output is correct
34 Correct 2641 ms 196516 KB Output is correct
35 Correct 3229 ms 237816 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65008 KB Output is correct
2 Correct 44 ms 64972 KB Output is correct
3 Correct 234 ms 65052 KB Output is correct
4 Correct 30 ms 64992 KB Output is correct
5 Correct 155 ms 64992 KB Output is correct
6 Correct 32 ms 65040 KB Output is correct
7 Correct 777 ms 123460 KB Output is correct
8 Correct 655 ms 151568 KB Output is correct
9 Correct 776 ms 139680 KB Output is correct
10 Correct 807 ms 155472 KB Output is correct
11 Correct 804 ms 155512 KB Output is correct
12 Correct 30 ms 64972 KB Output is correct
13 Correct 811 ms 138636 KB Output is correct
14 Correct 585 ms 153712 KB Output is correct
15 Correct 722 ms 126904 KB Output is correct
16 Correct 817 ms 154888 KB Output is correct
17 Correct 964 ms 136628 KB Output is correct
18 Correct 943 ms 135376 KB Output is correct
19 Correct 762 ms 151840 KB Output is correct
20 Correct 1077 ms 137556 KB Output is correct
21 Correct 1063 ms 151216 KB Output is correct
22 Correct 1044 ms 149888 KB Output is correct
23 Correct 1046 ms 133264 KB Output is correct
24 Correct 764 ms 146548 KB Output is correct
25 Correct 955 ms 118488 KB Output is correct
26 Correct 1099 ms 142452 KB Output is correct
27 Correct 2653 ms 161564 KB Output is correct
28 Correct 2569 ms 204320 KB Output is correct
29 Correct 2193 ms 228332 KB Output is correct
30 Correct 2762 ms 208324 KB Output is correct
31 Correct 2776 ms 237860 KB Output is correct
32 Correct 2654 ms 237836 KB Output is correct
33 Correct 815 ms 199960 KB Output is correct
34 Correct 2641 ms 196516 KB Output is correct
35 Correct 3229 ms 237816 KB Output is correct
36 Runtime error 225 ms 158028 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -