oj.uz

Submission #735725

# Submission time Handle Problem Language Result Execution time Memory
735725 2023-05-04T13:43:41 Z QwertyPi Escape Route (JOI21_escape_route) C++17
100 / 100
 8819 ms 1231448 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#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], Sc[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;
		}
	}
	
	for(int x = 0; x < N; x++){
		for(int y = 0; y < N; y++){
			for(int z = 0; z < N; z++){
				Sc[x][z].push_back({La[x][y], D[y][z]});
			}
		}
	}
	
	for(int u = 0; u < N; u++){
		for(int v = 0; v < N; v++){
			vector<pair<int, int>> vp;
			sort(Sc[u][v].begin(), Sc[u][v].end());
			for(auto [tx, tot] : Sc[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}); 
			}
			Sc[u][v] = vp;
		}
	}
	
	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);
		}
		
		ptr = lower_bound(Sc[U[i]][V[i]].begin(), Sc[U[i]][V[i]].end(), pair<int, int>{T[i], 0});
		if(ptr != Sc[U[i]][V[i]].end()){
			ans[i] = min(ans[i], ptr->second + S - T[i]);
		}
	}
	return ans; 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65356 KB Output is correct
2 Correct 31 ms 65388 KB Output is correct
3 Correct 254 ms 65420 KB Output is correct
4 Correct 25 ms 65420 KB Output is correct
5 Correct 32 ms 65368 KB Output is correct
6 Correct 30 ms 65364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 692 ms 161568 KB Output is correct
2 Correct 631 ms 174276 KB Output is correct
3 Correct 508 ms 161360 KB Output is correct
4 Correct 712 ms 174956 KB Output is correct
5 Correct 722 ms 176928 KB Output is correct
6 Correct 28 ms 65340 KB Output is correct
7 Correct 572 ms 162384 KB Output is correct
8 Correct 353 ms 141512 KB Output is correct
9 Correct 582 ms 153404 KB Output is correct
10 Correct 707 ms 174612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65356 KB Output is correct
2 Correct 31 ms 65388 KB Output is correct
3 Correct 254 ms 65420 KB Output is correct
4 Correct 25 ms 65420 KB Output is correct
5 Correct 32 ms 65368 KB Output is correct
6 Correct 30 ms 65364 KB Output is correct
7 Correct 692 ms 161568 KB Output is correct
8 Correct 631 ms 174276 KB Output is correct
9 Correct 508 ms 161360 KB Output is correct
10 Correct 712 ms 174956 KB Output is correct
11 Correct 722 ms 176928 KB Output is correct
12 Correct 28 ms 65340 KB Output is correct
13 Correct 572 ms 162384 KB Output is correct
14 Correct 353 ms 141512 KB Output is correct
15 Correct 582 ms 153404 KB Output is correct
16 Correct 707 ms 174612 KB Output is correct
17 Correct 872 ms 161172 KB Output is correct
18 Correct 850 ms 159136 KB Output is correct
19 Correct 755 ms 198548 KB Output is correct
20 Correct 584 ms 181836 KB Output is correct
21 Correct 893 ms 202672 KB Output is correct
22 Correct 927 ms 203788 KB Output is correct
23 Correct 608 ms 182824 KB Output is correct
24 Correct 383 ms 168876 KB Output is correct
25 Correct 737 ms 172896 KB Output is correct
26 Correct 975 ms 212468 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65356 KB Output is correct
2 Correct 31 ms 65388 KB Output is correct
3 Correct 254 ms 65420 KB Output is correct
4 Correct 25 ms 65420 KB Output is correct
5 Correct 32 ms 65368 KB Output is correct
6 Correct 30 ms 65364 KB Output is correct
7 Correct 692 ms 161568 KB Output is correct
8 Correct 631 ms 174276 KB Output is correct
9 Correct 508 ms 161360 KB Output is correct
10 Correct 712 ms 174956 KB Output is correct
11 Correct 722 ms 176928 KB Output is correct
12 Correct 28 ms 65340 KB Output is correct
13 Correct 572 ms 162384 KB Output is correct
14 Correct 353 ms 141512 KB Output is correct
15 Correct 582 ms 153404 KB Output is correct
16 Correct 707 ms 174612 KB Output is correct
17 Correct 872 ms 161172 KB Output is correct
18 Correct 850 ms 159136 KB Output is correct
19 Correct 755 ms 198548 KB Output is correct
20 Correct 584 ms 181836 KB Output is correct
21 Correct 893 ms 202672 KB Output is correct
22 Correct 927 ms 203788 KB Output is correct
23 Correct 608 ms 182824 KB Output is correct
24 Correct 383 ms 168876 KB Output is correct
25 Correct 737 ms 172896 KB Output is correct
26 Correct 975 ms 212468 KB Output is correct
27 Correct 2228 ms 362740 KB Output is correct
28 Correct 2326 ms 361504 KB Output is correct
29 Correct 1917 ms 381844 KB Output is correct
30 Correct 1501 ms 357264 KB Output is correct
31 Correct 2391 ms 410788 KB Output is correct
32 Correct 2335 ms 411452 KB Output is correct
33 Correct 392 ms 201056 KB Output is correct
34 Correct 2141 ms 374968 KB Output is correct
35 Correct 2358 ms 410948 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65356 KB Output is correct
2 Correct 31 ms 65388 KB Output is correct
3 Correct 254 ms 65420 KB Output is correct
4 Correct 25 ms 65420 KB Output is correct
5 Correct 32 ms 65368 KB Output is correct
6 Correct 30 ms 65364 KB Output is correct
7 Correct 692 ms 161568 KB Output is correct
8 Correct 631 ms 174276 KB Output is correct
9 Correct 508 ms 161360 KB Output is correct
10 Correct 712 ms 174956 KB Output is correct
11 Correct 722 ms 176928 KB Output is correct
12 Correct 28 ms 65340 KB Output is correct
13 Correct 572 ms 162384 KB Output is correct
14 Correct 353 ms 141512 KB Output is correct
15 Correct 582 ms 153404 KB Output is correct
16 Correct 707 ms 174612 KB Output is correct
17 Correct 872 ms 161172 KB Output is correct
18 Correct 850 ms 159136 KB Output is correct
19 Correct 755 ms 198548 KB Output is correct
20 Correct 584 ms 181836 KB Output is correct
21 Correct 893 ms 202672 KB Output is correct
22 Correct 927 ms 203788 KB Output is correct
23 Correct 608 ms 182824 KB Output is correct
24 Correct 383 ms 168876 KB Output is correct
25 Correct 737 ms 172896 KB Output is correct
26 Correct 975 ms 212468 KB Output is correct
27 Correct 2228 ms 362740 KB Output is correct
28 Correct 2326 ms 361504 KB Output is correct
29 Correct 1917 ms 381844 KB Output is correct
30 Correct 1501 ms 357264 KB Output is correct
31 Correct 2391 ms 410788 KB Output is correct
32 Correct 2335 ms 411452 KB Output is correct
33 Correct 392 ms 201056 KB Output is correct
34 Correct 2141 ms 374968 KB Output is correct
35 Correct 2358 ms 410948 KB Output is correct
36 Correct 8694 ms 1231448 KB Output is correct
37 Correct 8709 ms 1215608 KB Output is correct
38 Correct 6869 ms 1168132 KB Output is correct
39 Correct 8819 ms 1213480 KB Output is correct
40 Correct 8306 ms 1211384 KB Output is correct
41 Correct 442 ms 176240 KB Output is correct
42 Correct 8271 ms 1181488 KB Output is correct
43 Correct 8461 ms 1182960 KB Output is correct