oj.uz

Submission #735724

# Submission time Handle Problem Language Result Execution time Memory
735724 2023-05-04T13:37:49 Z QwertyPi Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 1227568 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], 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 28 ms 65392 KB Output is correct
2 Correct 35 ms 65428 KB Output is correct
3 Correct 274 ms 65492 KB Output is correct
4 Correct 28 ms 65492 KB Output is correct
5 Correct 33 ms 65380 KB Output is correct
6 Correct 32 ms 65432 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 161484 KB Output is correct
2 Correct 654 ms 174132 KB Output is correct
3 Correct 536 ms 161236 KB Output is correct
4 Correct 751 ms 174920 KB Output is correct
5 Correct 743 ms 176912 KB Output is correct
6 Correct 28 ms 65356 KB Output is correct
7 Correct 578 ms 162432 KB Output is correct
8 Correct 370 ms 141324 KB Output is correct
9 Correct 606 ms 153300 KB Output is correct
10 Correct 745 ms 174496 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 65392 KB Output is correct
2 Correct 35 ms 65428 KB Output is correct
3 Correct 274 ms 65492 KB Output is correct
4 Correct 28 ms 65492 KB Output is correct
5 Correct 33 ms 65380 KB Output is correct
6 Correct 32 ms 65432 KB Output is correct
7 Correct 712 ms 161484 KB Output is correct
8 Correct 654 ms 174132 KB Output is correct
9 Correct 536 ms 161236 KB Output is correct
10 Correct 751 ms 174920 KB Output is correct
11 Correct 743 ms 176912 KB Output is correct
12 Correct 28 ms 65356 KB Output is correct
13 Correct 578 ms 162432 KB Output is correct
14 Correct 370 ms 141324 KB Output is correct
15 Correct 606 ms 153300 KB Output is correct
16 Correct 745 ms 174496 KB Output is correct
17 Correct 934 ms 161096 KB Output is correct
18 Correct 925 ms 159100 KB Output is correct
19 Correct 797 ms 224792 KB Output is correct
20 Correct 606 ms 202816 KB Output is correct
21 Correct 937 ms 233548 KB Output is correct
22 Correct 971 ms 233404 KB Output is correct
23 Correct 648 ms 203416 KB Output is correct
24 Correct 392 ms 198632 KB Output is correct
25 Correct 756 ms 193064 KB Output is correct
26 Correct 958 ms 216352 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 65392 KB Output is correct
2 Correct 35 ms 65428 KB Output is correct
3 Correct 274 ms 65492 KB Output is correct
4 Correct 28 ms 65492 KB Output is correct
5 Correct 33 ms 65380 KB Output is correct
6 Correct 32 ms 65432 KB Output is correct
7 Correct 712 ms 161484 KB Output is correct
8 Correct 654 ms 174132 KB Output is correct
9 Correct 536 ms 161236 KB Output is correct
10 Correct 751 ms 174920 KB Output is correct
11 Correct 743 ms 176912 KB Output is correct
12 Correct 28 ms 65356 KB Output is correct
13 Correct 578 ms 162432 KB Output is correct
14 Correct 370 ms 141324 KB Output is correct
15 Correct 606 ms 153300 KB Output is correct
16 Correct 745 ms 174496 KB Output is correct
17 Correct 934 ms 161096 KB Output is correct
18 Correct 925 ms 159100 KB Output is correct
19 Correct 797 ms 224792 KB Output is correct
20 Correct 606 ms 202816 KB Output is correct
21 Correct 937 ms 233548 KB Output is correct
22 Correct 971 ms 233404 KB Output is correct
23 Correct 648 ms 203416 KB Output is correct
24 Correct 392 ms 198632 KB Output is correct
25 Correct 756 ms 193064 KB Output is correct
26 Correct 958 ms 216352 KB Output is correct
27 Correct 2393 ms 383472 KB Output is correct
28 Correct 2456 ms 382508 KB Output is correct
29 Correct 2072 ms 393248 KB Output is correct
30 Correct 1595 ms 374464 KB Output is correct
31 Correct 2559 ms 391688 KB Output is correct
32 Correct 2589 ms 392572 KB Output is correct
33 Correct 424 ms 181240 KB Output is correct
34 Correct 2192 ms 374880 KB Output is correct
35 Correct 2542 ms 389200 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 65392 KB Output is correct
2 Correct 35 ms 65428 KB Output is correct
3 Correct 274 ms 65492 KB Output is correct
4 Correct 28 ms 65492 KB Output is correct
5 Correct 33 ms 65380 KB Output is correct
6 Correct 32 ms 65432 KB Output is correct
7 Correct 712 ms 161484 KB Output is correct
8 Correct 654 ms 174132 KB Output is correct
9 Correct 536 ms 161236 KB Output is correct
10 Correct 751 ms 174920 KB Output is correct
11 Correct 743 ms 176912 KB Output is correct
12 Correct 28 ms 65356 KB Output is correct
13 Correct 578 ms 162432 KB Output is correct
14 Correct 370 ms 141324 KB Output is correct
15 Correct 606 ms 153300 KB Output is correct
16 Correct 745 ms 174496 KB Output is correct
17 Correct 934 ms 161096 KB Output is correct
18 Correct 925 ms 159100 KB Output is correct
19 Correct 797 ms 224792 KB Output is correct
20 Correct 606 ms 202816 KB Output is correct
21 Correct 937 ms 233548 KB Output is correct
22 Correct 971 ms 233404 KB Output is correct
23 Correct 648 ms 203416 KB Output is correct
24 Correct 392 ms 198632 KB Output is correct
25 Correct 756 ms 193064 KB Output is correct
26 Correct 958 ms 216352 KB Output is correct
27 Correct 2393 ms 383472 KB Output is correct
28 Correct 2456 ms 382508 KB Output is correct
29 Correct 2072 ms 393248 KB Output is correct
30 Correct 1595 ms 374464 KB Output is correct
31 Correct 2559 ms 391688 KB Output is correct
32 Correct 2589 ms 392572 KB Output is correct
33 Correct 424 ms 181240 KB Output is correct
34 Correct 2192 ms 374880 KB Output is correct
35 Correct 2542 ms 389200 KB Output is correct
36 Correct 8967 ms 1215740 KB Output is correct
37 Correct 8949 ms 1222624 KB Output is correct
38 Correct 6989 ms 1184808 KB Output is correct
39 Correct 8948 ms 1225168 KB Output is correct
40 Correct 8843 ms 1227568 KB Output is correct
41 Correct 473 ms 214360 KB Output is correct
42 Correct 8588 ms 1195236 KB Output is correct
43 Execution timed out 9016 ms 1215780 KB Time limit exceeded
44 Halted 0 ms 0 KB -