oj.uz

Submission #735709

# Submission time Handle Problem Language Result Execution time Memory
735709 2023-05-04T13:16:10 Z QwertyPi Escape Route (JOI21_escape_route) C++17
25 / 100
 9000 ms 172036 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];

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;
		}
	}
	
	vector<int> ans(Q, INF);
	for(int i = 0; i < Q; i++){
		ans[i] = S - T[i] + D[U[i]][V[i]];
		for(int m = 0; m < N; m++){
			auto ptr = lower_bound(Ti[U[i]][m].begin(), Ti[U[i]][m].end(), pair<int, int>{T[i], 0});
			if(ptr != Ti[U[i]][m].end()){
				ans[i] = min(ans[i], m == V[i] ? ptr->second : S - T[i] + D[m][V[i]]);
			}
		}
	}
	return ans; 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 65236 KB Output is correct
2 Correct 33 ms 65232 KB Output is correct
3 Correct 285 ms 65204 KB Output is correct
4 Correct 31 ms 65196 KB Output is correct
5 Correct 39 ms 65216 KB Output is correct
6 Correct 29 ms 65248 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5595 ms 156964 KB Output is correct
2 Correct 3485 ms 170940 KB Output is correct
3 Correct 1372 ms 157444 KB Output is correct
4 Correct 5029 ms 172036 KB Output is correct
5 Correct 5462 ms 171632 KB Output is correct
6 Correct 32 ms 65184 KB Output is correct
7 Correct 1810 ms 160232 KB Output is correct
8 Correct 610 ms 135528 KB Output is correct
9 Correct 4083 ms 149912 KB Output is correct
10 Correct 5531 ms 170660 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 65236 KB Output is correct
2 Correct 33 ms 65232 KB Output is correct
3 Correct 285 ms 65204 KB Output is correct
4 Correct 31 ms 65196 KB Output is correct
5 Correct 39 ms 65216 KB Output is correct
6 Correct 29 ms 65248 KB Output is correct
7 Correct 5595 ms 156964 KB Output is correct
8 Correct 3485 ms 170940 KB Output is correct
9 Correct 1372 ms 157444 KB Output is correct
10 Correct 5029 ms 172036 KB Output is correct
11 Correct 5462 ms 171632 KB Output is correct
12 Correct 32 ms 65184 KB Output is correct
13 Correct 1810 ms 160232 KB Output is correct
14 Correct 610 ms 135528 KB Output is correct
15 Correct 4083 ms 149912 KB Output is correct
16 Correct 5531 ms 170660 KB Output is correct
17 Correct 8523 ms 157136 KB Output is correct
18 Execution timed out 9006 ms 156784 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 65236 KB Output is correct
2 Correct 33 ms 65232 KB Output is correct
3 Correct 285 ms 65204 KB Output is correct
4 Correct 31 ms 65196 KB Output is correct
5 Correct 39 ms 65216 KB Output is correct
6 Correct 29 ms 65248 KB Output is correct
7 Correct 5595 ms 156964 KB Output is correct
8 Correct 3485 ms 170940 KB Output is correct
9 Correct 1372 ms 157444 KB Output is correct
10 Correct 5029 ms 172036 KB Output is correct
11 Correct 5462 ms 171632 KB Output is correct
12 Correct 32 ms 65184 KB Output is correct
13 Correct 1810 ms 160232 KB Output is correct
14 Correct 610 ms 135528 KB Output is correct
15 Correct 4083 ms 149912 KB Output is correct
16 Correct 5531 ms 170660 KB Output is correct
17 Correct 8523 ms 157136 KB Output is correct
18 Execution timed out 9006 ms 156784 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 65236 KB Output is correct
2 Correct 33 ms 65232 KB Output is correct
3 Correct 285 ms 65204 KB Output is correct
4 Correct 31 ms 65196 KB Output is correct
5 Correct 39 ms 65216 KB Output is correct
6 Correct 29 ms 65248 KB Output is correct
7 Correct 5595 ms 156964 KB Output is correct
8 Correct 3485 ms 170940 KB Output is correct
9 Correct 1372 ms 157444 KB Output is correct
10 Correct 5029 ms 172036 KB Output is correct
11 Correct 5462 ms 171632 KB Output is correct
12 Correct 32 ms 65184 KB Output is correct
13 Correct 1810 ms 160232 KB Output is correct
14 Correct 610 ms 135528 KB Output is correct
15 Correct 4083 ms 149912 KB Output is correct
16 Correct 5531 ms 170660 KB Output is correct
17 Correct 8523 ms 157136 KB Output is correct
18 Execution timed out 9006 ms 156784 KB Time limit exceeded
19 Halted 0 ms 0 KB -