oj.uz

Submission #735718

# Submission time Handle Problem Language Result Execution time Memory
735718 2023-05-04T13:26:58 Z QwertyPi Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 1184152 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define INF (1LL << 60)
using namespace std;

const int N = 91;

struct edge{
	int to, l, c;
};

vector<edge> G[N];

int S;

int norm(int tx){
	tx %= S;
	if(tx < 0) tx += S;
	return tx;
}

vector<pair<int, int>> Ti[N][N];
int D[N][N], La[N][N];

void add_data(int x, int y, int tx, int ty){
	if(tx <= -(INF >> 1) || ty >= (INF >> 1)) return;
	int rtx = norm(tx);
	int rty = ty + rtx - tx;
	int tot = rty - rtx;
	Ti[x][y].push_back({rtx, tot});
}

vector<int> from(int x, int t){
	vector<int> d(N, -INF); d[x] = t;
	priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;
	pq.push({t, x});
	while(!pq.empty()){
		auto [t, v] = pq.top(); pq.pop(); 
		if(d[v] != t) continue;
		for(auto [to, l, c] : G[v]){
			int tp = norm(t), nt;
			if(tp > c){ // back to c
				nt = t - (tp - c) - l;
			}else if(tp >= l){ // ok
				nt = t - l;
			}else{ // no last day
				nt = -INF;
			}
			if(nt > d[to]){
				d[to] = nt;
				pq.push({nt, to});
			}
		}
	}
	return d;
}

vector<int> to(int x, int t, bool allow_midnight){
	vector<int> d(N, INF); d[x] = t;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({t, x});
	while(!pq.empty()){
		auto [t, v] = pq.top(); pq.pop();
		if(d[v] != t) continue;
		for(auto [to, l, c] : G[v]){
			int tp = norm(t), nt;
			if(tp > c - l){ // next day
				nt = allow_midnight ? t + (S - tp) + l : INF;
			}else{ // ok
				nt = t + l;
			}
			if(nt < d[to]){
				d[to] = nt;
				pq.push({nt, to});
			}
		}
	}
	return d;
}


vector<int> calculate_necessary_time(int32_t N, int32_t M, int S, int32_t Q,
									 vector<int32_t> A, vector<int32_t> B, vector<int> L, vector<int> C, 
									 vector<int32_t> U, vector<int32_t> V, vector<int> T) {
	
	::S = S;
	for(int i = 0; i < M; i++){
		G[A[i]].push_back({B[i], L[i], C[i]});
		G[B[i]].push_back({A[i], L[i], C[i]});
	}
	
	for(int i = 0; i < M; i++){
		vector<int> d1, d2;
		
		d1 = from(A[i], C[i] - L[i]);
		d2 = to(B[i], C[i], false);
		for(int x = 0; x < N; x++){
			for(int y = 0; y < N; y++){
				add_data(x, y, d1[x], d2[y]);
			}
		}
		
		d1 = from(B[i], C[i] - L[i]);
		d2 = to(A[i], C[i], false);
		for(int x = 0; x < N; x++){
			for(int y = 0; y < N; y++){
				add_data(x, y, d1[x], d2[y]);
			}
		}
	}
	
	for(int i = 0; i < N; i++){
		vector<int> d = to(i, 0, true);
		for(int j = 0; j < N; j++){
			D[i][j] = d[j];
		}
	}
	
	for(int u = 0; u < N; u++){
		for(int v = 0; v < N; v++){
			vector<pair<int, int>> vp;
			sort(Ti[u][v].begin(), Ti[u][v].end());
			for(auto [tx, tot] : Ti[u][v]){
				while(!vp.empty() && vp.back().second >= tot) vp.pop_back();
				if(!vp.empty() && vp.back().first == tx) continue;
				vp.push_back({tx, tot}); 
			}
			Ti[u][v] = vp;
		}
	}
	
	for(int u = 0; u < N; u++){
		for(int v = 0; v < N; v++){
			if(u != v) La[u][v] = Ti[u][v].empty() ? -1 : (--Ti[u][v].end())->first;
			else La[u][v] = S;
		}
	}
	
	vector<int> ans(Q, INF);
	for(int i = 0; i < Q; i++){
		auto ptr = lower_bound(Ti[U[i]][V[i]].begin(), Ti[U[i]][V[i]].end(), pair<int, int>{T[i], 0});
		if(ptr != Ti[U[i]][V[i]].end()){
			ans[i] = min(ans[i], ptr->second);
		}
		
		for(int m = 0; m < N; m++){
			if(T[i] <= La[U[i]][m]){
				ans[i] = min(ans[i], S - T[i] + D[m][V[i]]);
			}
		}
	}
	return ans; 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65192 KB Output is correct
2 Correct 29 ms 65228 KB Output is correct
3 Correct 270 ms 65296 KB Output is correct
4 Correct 26 ms 65236 KB Output is correct
5 Correct 30 ms 65240 KB Output is correct
6 Correct 25 ms 65152 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1034 ms 160092 KB Output is correct
2 Correct 954 ms 171040 KB Output is correct
3 Correct 768 ms 156992 KB Output is correct
4 Correct 1020 ms 171056 KB Output is correct
5 Correct 1014 ms 170768 KB Output is correct
6 Correct 27 ms 65124 KB Output is correct
7 Correct 834 ms 159792 KB Output is correct
8 Correct 433 ms 134640 KB Output is correct
9 Correct 888 ms 149660 KB Output is correct
10 Correct 1016 ms 169912 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65192 KB Output is correct
2 Correct 29 ms 65228 KB Output is correct
3 Correct 270 ms 65296 KB Output is correct
4 Correct 26 ms 65236 KB Output is correct
5 Correct 30 ms 65240 KB Output is correct
6 Correct 25 ms 65152 KB Output is correct
7 Correct 1034 ms 160092 KB Output is correct
8 Correct 954 ms 171040 KB Output is correct
9 Correct 768 ms 156992 KB Output is correct
10 Correct 1020 ms 171056 KB Output is correct
11 Correct 1014 ms 170768 KB Output is correct
12 Correct 27 ms 65124 KB Output is correct
13 Correct 834 ms 159792 KB Output is correct
14 Correct 433 ms 134640 KB Output is correct
15 Correct 888 ms 149660 KB Output is correct
16 Correct 1016 ms 169912 KB Output is correct
17 Correct 1132 ms 156864 KB Output is correct
18 Correct 1268 ms 156352 KB Output is correct
19 Correct 1099 ms 224592 KB Output is correct
20 Correct 862 ms 202732 KB Output is correct
21 Correct 1314 ms 233104 KB Output is correct
22 Correct 1365 ms 230780 KB Output is correct
23 Correct 980 ms 201824 KB Output is correct
24 Correct 484 ms 194096 KB Output is correct
25 Correct 1142 ms 189852 KB Output is correct
26 Correct 1496 ms 233468 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65192 KB Output is correct
2 Correct 29 ms 65228 KB Output is correct
3 Correct 270 ms 65296 KB Output is correct
4 Correct 26 ms 65236 KB Output is correct
5 Correct 30 ms 65240 KB Output is correct
6 Correct 25 ms 65152 KB Output is correct
7 Correct 1034 ms 160092 KB Output is correct
8 Correct 954 ms 171040 KB Output is correct
9 Correct 768 ms 156992 KB Output is correct
10 Correct 1020 ms 171056 KB Output is correct
11 Correct 1014 ms 170768 KB Output is correct
12 Correct 27 ms 65124 KB Output is correct
13 Correct 834 ms 159792 KB Output is correct
14 Correct 433 ms 134640 KB Output is correct
15 Correct 888 ms 149660 KB Output is correct
16 Correct 1016 ms 169912 KB Output is correct
17 Correct 1132 ms 156864 KB Output is correct
18 Correct 1268 ms 156352 KB Output is correct
19 Correct 1099 ms 224592 KB Output is correct
20 Correct 862 ms 202732 KB Output is correct
21 Correct 1314 ms 233104 KB Output is correct
22 Correct 1365 ms 230780 KB Output is correct
23 Correct 980 ms 201824 KB Output is correct
24 Correct 484 ms 194096 KB Output is correct
25 Correct 1142 ms 189852 KB Output is correct
26 Correct 1496 ms 233468 KB Output is correct
27 Correct 3245 ms 380496 KB Output is correct
28 Correct 3375 ms 381532 KB Output is correct
29 Correct 2620 ms 399012 KB Output is correct
30 Correct 2093 ms 372884 KB Output is correct
31 Correct 3388 ms 407660 KB Output is correct
32 Correct 3449 ms 406416 KB Output is correct
33 Correct 544 ms 197320 KB Output is correct
34 Correct 3066 ms 368948 KB Output is correct
35 Correct 3378 ms 405312 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65192 KB Output is correct
2 Correct 29 ms 65228 KB Output is correct
3 Correct 270 ms 65296 KB Output is correct
4 Correct 26 ms 65236 KB Output is correct
5 Correct 30 ms 65240 KB Output is correct
6 Correct 25 ms 65152 KB Output is correct
7 Correct 1034 ms 160092 KB Output is correct
8 Correct 954 ms 171040 KB Output is correct
9 Correct 768 ms 156992 KB Output is correct
10 Correct 1020 ms 171056 KB Output is correct
11 Correct 1014 ms 170768 KB Output is correct
12 Correct 27 ms 65124 KB Output is correct
13 Correct 834 ms 159792 KB Output is correct
14 Correct 433 ms 134640 KB Output is correct
15 Correct 888 ms 149660 KB Output is correct
16 Correct 1016 ms 169912 KB Output is correct
17 Correct 1132 ms 156864 KB Output is correct
18 Correct 1268 ms 156352 KB Output is correct
19 Correct 1099 ms 224592 KB Output is correct
20 Correct 862 ms 202732 KB Output is correct
21 Correct 1314 ms 233104 KB Output is correct
22 Correct 1365 ms 230780 KB Output is correct
23 Correct 980 ms 201824 KB Output is correct
24 Correct 484 ms 194096 KB Output is correct
25 Correct 1142 ms 189852 KB Output is correct
26 Correct 1496 ms 233468 KB Output is correct
27 Correct 3245 ms 380496 KB Output is correct
28 Correct 3375 ms 381532 KB Output is correct
29 Correct 2620 ms 399012 KB Output is correct
30 Correct 2093 ms 372884 KB Output is correct
31 Correct 3388 ms 407660 KB Output is correct
32 Correct 3449 ms 406416 KB Output is correct
33 Correct 544 ms 197320 KB Output is correct
34 Correct 3066 ms 368948 KB Output is correct
35 Correct 3378 ms 405312 KB Output is correct
36 Execution timed out 9172 ms 1184152 KB Time limit exceeded
37 Halted 0 ms 0 KB -