oj.uz

Submission #735697

# Submission time Handle Problem Language Result Execution time Memory
735697 2023-05-04T13:09:14 Z QwertyPi Escape Route (JOI21_escape_route) C++17
25 / 100
 9000 ms 231240 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
#define int long long
#define INF (1LL << 60)
using namespace std;

const int N = 101;

struct timestamp{
	int day = N, byou = 0;
	bool operator< (const timestamp& o) const {
		return day > o.day || day == o.day && byou < o.byou;
	}
};

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

vector<edge> G[N];

int S;

int norm(int x){
	return (x % S + S) % S;
}

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 = ((tx % S) + S) % S;
	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; 
}

Compilation message

escape_route.cpp: In member function 'bool timestamp::operator<(const timestamp&) const':
escape_route.cpp:12:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   12 |   return day > o.day || day == o.day && byou < o.byou;
      |                         ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65364 KB Output is correct
2 Correct 30 ms 65240 KB Output is correct
3 Correct 272 ms 65312 KB Output is correct
4 Correct 25 ms 65236 KB Output is correct
5 Correct 29 ms 65272 KB Output is correct
6 Correct 25 ms 65236 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4897 ms 199444 KB Output is correct
2 Correct 2916 ms 221608 KB Output is correct
3 Correct 1218 ms 197932 KB Output is correct
4 Correct 4833 ms 231240 KB Output is correct
5 Correct 4873 ms 230536 KB Output is correct
6 Correct 28 ms 65228 KB Output is correct
7 Correct 1635 ms 201812 KB Output is correct
8 Correct 587 ms 194552 KB Output is correct
9 Correct 4013 ms 191620 KB Output is correct
10 Correct 5337 ms 230100 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65364 KB Output is correct
2 Correct 30 ms 65240 KB Output is correct
3 Correct 272 ms 65312 KB Output is correct
4 Correct 25 ms 65236 KB Output is correct
5 Correct 29 ms 65272 KB Output is correct
6 Correct 25 ms 65236 KB Output is correct
7 Correct 4897 ms 199444 KB Output is correct
8 Correct 2916 ms 221608 KB Output is correct
9 Correct 1218 ms 197932 KB Output is correct
10 Correct 4833 ms 231240 KB Output is correct
11 Correct 4873 ms 230536 KB Output is correct
12 Correct 28 ms 65228 KB Output is correct
13 Correct 1635 ms 201812 KB Output is correct
14 Correct 587 ms 194552 KB Output is correct
15 Correct 4013 ms 191620 KB Output is correct
16 Correct 5337 ms 230100 KB Output is correct
17 Correct 8119 ms 201316 KB Output is correct
18 Execution timed out 9097 ms 165692 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65364 KB Output is correct
2 Correct 30 ms 65240 KB Output is correct
3 Correct 272 ms 65312 KB Output is correct
4 Correct 25 ms 65236 KB Output is correct
5 Correct 29 ms 65272 KB Output is correct
6 Correct 25 ms 65236 KB Output is correct
7 Correct 4897 ms 199444 KB Output is correct
8 Correct 2916 ms 221608 KB Output is correct
9 Correct 1218 ms 197932 KB Output is correct
10 Correct 4833 ms 231240 KB Output is correct
11 Correct 4873 ms 230536 KB Output is correct
12 Correct 28 ms 65228 KB Output is correct
13 Correct 1635 ms 201812 KB Output is correct
14 Correct 587 ms 194552 KB Output is correct
15 Correct 4013 ms 191620 KB Output is correct
16 Correct 5337 ms 230100 KB Output is correct
17 Correct 8119 ms 201316 KB Output is correct
18 Execution timed out 9097 ms 165692 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65364 KB Output is correct
2 Correct 30 ms 65240 KB Output is correct
3 Correct 272 ms 65312 KB Output is correct
4 Correct 25 ms 65236 KB Output is correct
5 Correct 29 ms 65272 KB Output is correct
6 Correct 25 ms 65236 KB Output is correct
7 Correct 4897 ms 199444 KB Output is correct
8 Correct 2916 ms 221608 KB Output is correct
9 Correct 1218 ms 197932 KB Output is correct
10 Correct 4833 ms 231240 KB Output is correct
11 Correct 4873 ms 230536 KB Output is correct
12 Correct 28 ms 65228 KB Output is correct
13 Correct 1635 ms 201812 KB Output is correct
14 Correct 587 ms 194552 KB Output is correct
15 Correct 4013 ms 191620 KB Output is correct
16 Correct 5337 ms 230100 KB Output is correct
17 Correct 8119 ms 201316 KB Output is correct
18 Execution timed out 9097 ms 165692 KB Time limit exceeded
19 Halted 0 ms 0 KB -