oj.uz

Submission #429220

# Submission time Handle Problem Language Result Execution time Memory
429220 2021-06-15T19:08:41 Z amoo_safar Escape Route (JOI21_escape_route) C++17
35 / 100
 1147 ms 195592 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 = 42;
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 29 ms 64980 KB Output is correct
2 Correct 48 ms 65016 KB Output is correct
3 Correct 211 ms 65072 KB Output is correct
4 Correct 28 ms 65036 KB Output is correct
5 Correct 157 ms 64972 KB Output is correct
6 Correct 34 ms 64972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 117200 KB Output is correct
2 Correct 681 ms 183476 KB Output is correct
3 Correct 818 ms 164488 KB Output is correct
4 Correct 869 ms 193100 KB Output is correct
5 Correct 858 ms 193056 KB Output is correct
6 Correct 33 ms 64972 KB Output is correct
7 Correct 835 ms 164032 KB Output is correct
8 Correct 655 ms 195592 KB Output is correct
9 Correct 795 ms 154988 KB Output is correct
10 Correct 887 ms 192516 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64980 KB Output is correct
2 Correct 48 ms 65016 KB Output is correct
3 Correct 211 ms 65072 KB Output is correct
4 Correct 28 ms 65036 KB Output is correct
5 Correct 157 ms 64972 KB Output is correct
6 Correct 34 ms 64972 KB Output is correct
7 Correct 703 ms 117200 KB Output is correct
8 Correct 681 ms 183476 KB Output is correct
9 Correct 818 ms 164488 KB Output is correct
10 Correct 869 ms 193100 KB Output is correct
11 Correct 858 ms 193056 KB Output is correct
12 Correct 33 ms 64972 KB Output is correct
13 Correct 835 ms 164032 KB Output is correct
14 Correct 655 ms 195592 KB Output is correct
15 Correct 795 ms 154988 KB Output is correct
16 Correct 887 ms 192516 KB Output is correct
17 Correct 1071 ms 162800 KB Output is correct
18 Correct 1020 ms 161628 KB Output is correct
19 Correct 872 ms 183288 KB Output is correct
20 Correct 1094 ms 165292 KB Output is correct
21 Correct 1147 ms 193868 KB Output is correct
22 Correct 1058 ms 194376 KB Output is correct
23 Correct 997 ms 165680 KB Output is correct
24 Correct 760 ms 194148 KB Output is correct
25 Correct 941 ms 155812 KB Output is correct
26 Correct 1114 ms 193576 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64980 KB Output is correct
2 Correct 48 ms 65016 KB Output is correct
3 Correct 211 ms 65072 KB Output is correct
4 Correct 28 ms 65036 KB Output is correct
5 Correct 157 ms 64972 KB Output is correct
6 Correct 34 ms 64972 KB Output is correct
7 Correct 703 ms 117200 KB Output is correct
8 Correct 681 ms 183476 KB Output is correct
9 Correct 818 ms 164488 KB Output is correct
10 Correct 869 ms 193100 KB Output is correct
11 Correct 858 ms 193056 KB Output is correct
12 Correct 33 ms 64972 KB Output is correct
13 Correct 835 ms 164032 KB Output is correct
14 Correct 655 ms 195592 KB Output is correct
15 Correct 795 ms 154988 KB Output is correct
16 Correct 887 ms 192516 KB Output is correct
17 Correct 1071 ms 162800 KB Output is correct
18 Correct 1020 ms 161628 KB Output is correct
19 Correct 872 ms 183288 KB Output is correct
20 Correct 1094 ms 165292 KB Output is correct
21 Correct 1147 ms 193868 KB Output is correct
22 Correct 1058 ms 194376 KB Output is correct
23 Correct 997 ms 165680 KB Output is correct
24 Correct 760 ms 194148 KB Output is correct
25 Correct 941 ms 155812 KB Output is correct
26 Correct 1114 ms 193576 KB Output is correct
27 Runtime error 234 ms 156636 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64980 KB Output is correct
2 Correct 48 ms 65016 KB Output is correct
3 Correct 211 ms 65072 KB Output is correct
4 Correct 28 ms 65036 KB Output is correct
5 Correct 157 ms 64972 KB Output is correct
6 Correct 34 ms 64972 KB Output is correct
7 Correct 703 ms 117200 KB Output is correct
8 Correct 681 ms 183476 KB Output is correct
9 Correct 818 ms 164488 KB Output is correct
10 Correct 869 ms 193100 KB Output is correct
11 Correct 858 ms 193056 KB Output is correct
12 Correct 33 ms 64972 KB Output is correct
13 Correct 835 ms 164032 KB Output is correct
14 Correct 655 ms 195592 KB Output is correct
15 Correct 795 ms 154988 KB Output is correct
16 Correct 887 ms 192516 KB Output is correct
17 Correct 1071 ms 162800 KB Output is correct
18 Correct 1020 ms 161628 KB Output is correct
19 Correct 872 ms 183288 KB Output is correct
20 Correct 1094 ms 165292 KB Output is correct
21 Correct 1147 ms 193868 KB Output is correct
22 Correct 1058 ms 194376 KB Output is correct
23 Correct 997 ms 165680 KB Output is correct
24 Correct 760 ms 194148 KB Output is correct
25 Correct 941 ms 155812 KB Output is correct
26 Correct 1114 ms 193576 KB Output is correct
27 Runtime error 234 ms 156636 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -