oj.uz

Submission #900059

# Submission time Handle Problem Language Result Execution time Memory
900059 2024-01-07T14:26:39 Z marvinthang Escape Route (JOI21_escape_route) C++17
100 / 100
 2067 ms 206868 KB 
/*************************************
*    author: marvinthang             *
*    created: 07.01.2024 16:50:40    *
*************************************/
 
#include "escape_route.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
	#include "debug.h"
#else
	#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
	#define DB(...) 23
	#define db(...) 23
	#define debug(...) 23
#endif
 
template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { return a > b ? a = b, true : false; }
template <class A, class B> bool maximize(A &a, B b)  { return a < b ? a = b, true : false; }
 
// end of template
 
const long long INF = 1e18;
 
vector <long long> calculate_necessary_time(
	int N, int M, long long S, int Q, vector <int> A, vector <int> B,
	vector <long long> L, vector <long long> C, vector <int> U,
	vector <int> V, vector <long long> T) {
	vector <vector <int>> adj(N);
	REP(i, M) {
		adj[A[i]].push_back(i);
		adj[B[i]].push_back(i);
	}

	vector <bool> used(N);
	vector dist(N, vector(N, INF)), max_time(N, vector(N, -1LL));

	auto solve_dist = [&] (int s, long long d, vector <long long> &dist, bool one_day) {
		fill(ALL(used), false);
		dist[s] = d;
		REP(love, N - 1) {
			int u = -1;
			REP(i, N) if (!used[i] && (u == -1 || dist[i] < dist[u])) u = i;
			used[u] = true;
			long long x = dist[u] % S;
			for (int i: adj[u]) {
				int v = A[i] ^ B[i] ^ u;
				minimize(dist[v], dist[u] + L[i] + (x + L[i] <= C[i] ? 0 : one_day ? INF : S - x));
			}
		}
	};

	auto solve_max_time = [&] (int s, long long d, vector <long long> &max_time) {
		fill(ALL(used), false);
		max_time[s] = d;
		REP(love, N - 1) {
			int u = -1;
			REP(i, N) if (!used[i] && (u == -1 || max_time[i] > max_time[u])) u = i;
			used[u] = true;
			for (int i: adj[u]) {
				int v = A[i] ^ B[i] ^ u;
				maximize(max_time[v], min(max_time[u], C[i]) - L[i]);
			}
		}
	};

	REP(u, N) {
		solve_dist(u, 0, dist[u], false);
		solve_max_time(u, S, max_time[u]);
	}

	vector dist_edge(2 * M, vector(N, INF)), max_time_edge(2 * M, vector(N, -1LL));

	REP(i, M) {
		solve_dist(A[i], C[i], dist_edge[i], true);
		solve_max_time(A[i], C[i], max_time_edge[i]);
		solve_dist(B[i], C[i], dist_edge[i + M], true);
		solve_max_time(B[i], C[i], max_time_edge[i + M]);
	}

	vector <long long> res(Q, INF);
	vector <vector <pair <long long, int>>> queriesAt(N);
	REP(i, Q) {
		REP(w, N) if (T[i] <= max_time[w][U[i]])
			minimize(res[i], S + dist[w][V[i]] - T[i]);
		if (dist[U[i]][V[i]] < S) queriesAt[U[i]].emplace_back(T[i], -1 - i);
	}
	REP(s, N) {
		REP(i, 2 * M) queriesAt[s].emplace_back(max_time_edge[i][s], i);
		sort(queriesAt[s].rbegin(), queriesAt[s].rend());
		vector <long long> dist(N, INF);
		for (auto [t, i]: queriesAt[s]) {
			if (i < 0) {
				i = -1 - i;
				minimize(res[i], dist[V[i]]);
			} else {
				REP(v, N) minimize(dist[v], dist_edge[i][v] - t);
			}
		}
	}
	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 65112 KB Output is correct
2 Correct 15 ms 65112 KB Output is correct
3 Correct 47 ms 65116 KB Output is correct
4 Correct 9 ms 65112 KB Output is correct
5 Correct 33 ms 65180 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 181608 KB Output is correct
2 Correct 813 ms 190100 KB Output is correct
3 Correct 716 ms 179980 KB Output is correct
4 Correct 841 ms 197988 KB Output is correct
5 Correct 825 ms 199232 KB Output is correct
6 Correct 8 ms 65112 KB Output is correct
7 Correct 764 ms 181740 KB Output is correct
8 Correct 328 ms 193912 KB Output is correct
9 Correct 740 ms 182340 KB Output is correct
10 Correct 835 ms 199140 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 65112 KB Output is correct
2 Correct 15 ms 65112 KB Output is correct
3 Correct 47 ms 65116 KB Output is correct
4 Correct 9 ms 65112 KB Output is correct
5 Correct 33 ms 65180 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct
7 Correct 757 ms 181608 KB Output is correct
8 Correct 813 ms 190100 KB Output is correct
9 Correct 716 ms 179980 KB Output is correct
10 Correct 841 ms 197988 KB Output is correct
11 Correct 825 ms 199232 KB Output is correct
12 Correct 8 ms 65112 KB Output is correct
13 Correct 764 ms 181740 KB Output is correct
14 Correct 328 ms 193912 KB Output is correct
15 Correct 740 ms 182340 KB Output is correct
16 Correct 835 ms 199140 KB Output is correct
17 Correct 763 ms 165716 KB Output is correct
18 Correct 737 ms 164728 KB Output is correct
19 Correct 808 ms 178388 KB Output is correct
20 Correct 745 ms 166224 KB Output is correct
21 Correct 816 ms 185488 KB Output is correct
22 Correct 835 ms 185344 KB Output is correct
23 Correct 776 ms 166716 KB Output is correct
24 Correct 389 ms 197132 KB Output is correct
25 Correct 739 ms 165200 KB Output is correct
26 Correct 818 ms 185180 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 65112 KB Output is correct
2 Correct 15 ms 65112 KB Output is correct
3 Correct 47 ms 65116 KB Output is correct
4 Correct 9 ms 65112 KB Output is correct
5 Correct 33 ms 65180 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct
7 Correct 757 ms 181608 KB Output is correct
8 Correct 813 ms 190100 KB Output is correct
9 Correct 716 ms 179980 KB Output is correct
10 Correct 841 ms 197988 KB Output is correct
11 Correct 825 ms 199232 KB Output is correct
12 Correct 8 ms 65112 KB Output is correct
13 Correct 764 ms 181740 KB Output is correct
14 Correct 328 ms 193912 KB Output is correct
15 Correct 740 ms 182340 KB Output is correct
16 Correct 835 ms 199140 KB Output is correct
17 Correct 763 ms 165716 KB Output is correct
18 Correct 737 ms 164728 KB Output is correct
19 Correct 808 ms 178388 KB Output is correct
20 Correct 745 ms 166224 KB Output is correct
21 Correct 816 ms 185488 KB Output is correct
22 Correct 835 ms 185344 KB Output is correct
23 Correct 776 ms 166716 KB Output is correct
24 Correct 389 ms 197132 KB Output is correct
25 Correct 739 ms 165200 KB Output is correct
26 Correct 818 ms 185180 KB Output is correct
27 Correct 1014 ms 172092 KB Output is correct
28 Correct 995 ms 171352 KB Output is correct
29 Correct 1037 ms 180620 KB Output is correct
30 Correct 1025 ms 170748 KB Output is correct
31 Correct 1085 ms 189372 KB Output is correct
32 Correct 1084 ms 188944 KB Output is correct
33 Correct 417 ms 197512 KB Output is correct
34 Correct 994 ms 170820 KB Output is correct
35 Correct 1096 ms 188224 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 65112 KB Output is correct
2 Correct 15 ms 65112 KB Output is correct
3 Correct 47 ms 65116 KB Output is correct
4 Correct 9 ms 65112 KB Output is correct
5 Correct 33 ms 65180 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct
7 Correct 757 ms 181608 KB Output is correct
8 Correct 813 ms 190100 KB Output is correct
9 Correct 716 ms 179980 KB Output is correct
10 Correct 841 ms 197988 KB Output is correct
11 Correct 825 ms 199232 KB Output is correct
12 Correct 8 ms 65112 KB Output is correct
13 Correct 764 ms 181740 KB Output is correct
14 Correct 328 ms 193912 KB Output is correct
15 Correct 740 ms 182340 KB Output is correct
16 Correct 835 ms 199140 KB Output is correct
17 Correct 763 ms 165716 KB Output is correct
18 Correct 737 ms 164728 KB Output is correct
19 Correct 808 ms 178388 KB Output is correct
20 Correct 745 ms 166224 KB Output is correct
21 Correct 816 ms 185488 KB Output is correct
22 Correct 835 ms 185344 KB Output is correct
23 Correct 776 ms 166716 KB Output is correct
24 Correct 389 ms 197132 KB Output is correct
25 Correct 739 ms 165200 KB Output is correct
26 Correct 818 ms 185180 KB Output is correct
27 Correct 1014 ms 172092 KB Output is correct
28 Correct 995 ms 171352 KB Output is correct
29 Correct 1037 ms 180620 KB Output is correct
30 Correct 1025 ms 170748 KB Output is correct
31 Correct 1085 ms 189372 KB Output is correct
32 Correct 1084 ms 188944 KB Output is correct
33 Correct 417 ms 197512 KB Output is correct
34 Correct 994 ms 170820 KB Output is correct
35 Correct 1096 ms 188224 KB Output is correct
36 Correct 1968 ms 190224 KB Output is correct
37 Correct 1980 ms 189192 KB Output is correct
38 Correct 1961 ms 190288 KB Output is correct
39 Correct 2067 ms 206868 KB Output is correct
40 Correct 2041 ms 206656 KB Output is correct
41 Correct 519 ms 197748 KB Output is correct
42 Correct 2029 ms 189116 KB Output is correct
43 Correct 2021 ms 188228 KB Output is correct