oj.uz

Submission #900033

# Submission time Handle Problem Language Result Execution time Memory
900033 2024-01-07T13:05:44 Z marvinthang Escape Route (JOI21_escape_route) C++17
35 / 100
 9000 ms 196736 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));
	REP(s, N) {
		fill(ALL(used), false);
		dist[s][s] = 0;
		REP(love, N - 1) {
			int u = -1;
			REP(i, N) if (!used[i] && (u == -1 || dist[s][i] < dist[s][u])) u = i;
			used[u] = true;
			long long x = dist[s][u] % S;
			for (int i: adj[u]) {
				int v = A[i] ^ B[i] ^ u;
				minimize(dist[s][v], dist[s][u] + L[i] + (x + L[i] > C[i] ? S - x : 0));
			}
		}

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

	vector <long long> res(Q, INF);
	vector <vector <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]].push_back(i);
	}
	REP(s, N) {
		sort(ALL(queriesAt[s]), [&] (int x, int y) { return T[x] > T[y]; });
		vector <long long> dist(N, INF);
		dist[s] = 0;
		set <pair <long long, int>> blocked_edge;
		fill(ALL(used), false);
		for (int i: queriesAt[s]) {
			long long t = T[i];
			while (!blocked_edge.empty() && blocked_edge.rbegin()->fi >= t) {
				int i = blocked_edge.rbegin()->se;
				if (minimize(dist[A[i]], dist[B[i]] + L[i])) used[A[i]] = false;
				else if (minimize(dist[B[i]], dist[A[i]] + L[i])) used[B[i]] = false;
				blocked_edge.erase(*blocked_edge.rbegin());
			}
			while (true) {
				int u = -1;
				REP(i, N) if (!used[i] && (u == -1 || dist[i] < dist[u])) u = i;
				if (u == -1) break;
				used[u] = true;
				for (int i: adj[u]) {
					int v = A[i] ^ B[i] ^ u;
					if (dist[v] <= dist[u]) continue;
					if (t + dist[u] <= C[i] - L[i]) {
						if (minimize(dist[v], dist[u] + L[i])) used[v] = false;
					} else {
						blocked_edge.emplace(C[i] - L[i] - dist[u], i);
					}
				}
			}
			minimize(res[i], dist[V[i]]);
		}
	}
	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65116 KB Output is correct
2 Correct 12 ms 65116 KB Output is correct
3 Correct 29 ms 65116 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 8 ms 65116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1304 ms 112208 KB Output is correct
2 Correct 1419 ms 173808 KB Output is correct
3 Correct 1300 ms 153580 KB Output is correct
4 Correct 1467 ms 183272 KB Output is correct
5 Correct 1466 ms 183556 KB Output is correct
6 Correct 8 ms 65116 KB Output is correct
7 Correct 1383 ms 155100 KB Output is correct
8 Correct 385 ms 194160 KB Output is correct
9 Correct 1303 ms 155016 KB Output is correct
10 Correct 1506 ms 182936 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65116 KB Output is correct
2 Correct 12 ms 65116 KB Output is correct
3 Correct 29 ms 65116 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 8 ms 65116 KB Output is correct
7 Correct 1304 ms 112208 KB Output is correct
8 Correct 1419 ms 173808 KB Output is correct
9 Correct 1300 ms 153580 KB Output is correct
10 Correct 1467 ms 183272 KB Output is correct
11 Correct 1466 ms 183556 KB Output is correct
12 Correct 8 ms 65116 KB Output is correct
13 Correct 1383 ms 155100 KB Output is correct
14 Correct 385 ms 194160 KB Output is correct
15 Correct 1303 ms 155016 KB Output is correct
16 Correct 1506 ms 182936 KB Output is correct
17 Correct 1664 ms 157148 KB Output is correct
18 Correct 1809 ms 157048 KB Output is correct
19 Correct 1997 ms 179016 KB Output is correct
20 Correct 1234 ms 157836 KB Output is correct
21 Correct 1985 ms 187792 KB Output is correct
22 Correct 1983 ms 187448 KB Output is correct
23 Correct 1292 ms 157052 KB Output is correct
24 Correct 430 ms 196736 KB Output is correct
25 Correct 1634 ms 157060 KB Output is correct
26 Correct 2040 ms 187120 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65116 KB Output is correct
2 Correct 12 ms 65116 KB Output is correct
3 Correct 29 ms 65116 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 8 ms 65116 KB Output is correct
7 Correct 1304 ms 112208 KB Output is correct
8 Correct 1419 ms 173808 KB Output is correct
9 Correct 1300 ms 153580 KB Output is correct
10 Correct 1467 ms 183272 KB Output is correct
11 Correct 1466 ms 183556 KB Output is correct
12 Correct 8 ms 65116 KB Output is correct
13 Correct 1383 ms 155100 KB Output is correct
14 Correct 385 ms 194160 KB Output is correct
15 Correct 1303 ms 155016 KB Output is correct
16 Correct 1506 ms 182936 KB Output is correct
17 Correct 1664 ms 157148 KB Output is correct
18 Correct 1809 ms 157048 KB Output is correct
19 Correct 1997 ms 179016 KB Output is correct
20 Correct 1234 ms 157836 KB Output is correct
21 Correct 1985 ms 187792 KB Output is correct
22 Correct 1983 ms 187448 KB Output is correct
23 Correct 1292 ms 157052 KB Output is correct
24 Correct 430 ms 196736 KB Output is correct
25 Correct 1634 ms 157060 KB Output is correct
26 Correct 2040 ms 187120 KB Output is correct
27 Correct 4783 ms 159684 KB Output is correct
28 Correct 7021 ms 162776 KB Output is correct
29 Correct 8278 ms 186660 KB Output is correct
30 Correct 1494 ms 158764 KB Output is correct
31 Correct 8615 ms 195488 KB Output is correct
32 Execution timed out 9019 ms 194988 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65116 KB Output is correct
2 Correct 12 ms 65116 KB Output is correct
3 Correct 29 ms 65116 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 8 ms 65116 KB Output is correct
7 Correct 1304 ms 112208 KB Output is correct
8 Correct 1419 ms 173808 KB Output is correct
9 Correct 1300 ms 153580 KB Output is correct
10 Correct 1467 ms 183272 KB Output is correct
11 Correct 1466 ms 183556 KB Output is correct
12 Correct 8 ms 65116 KB Output is correct
13 Correct 1383 ms 155100 KB Output is correct
14 Correct 385 ms 194160 KB Output is correct
15 Correct 1303 ms 155016 KB Output is correct
16 Correct 1506 ms 182936 KB Output is correct
17 Correct 1664 ms 157148 KB Output is correct
18 Correct 1809 ms 157048 KB Output is correct
19 Correct 1997 ms 179016 KB Output is correct
20 Correct 1234 ms 157836 KB Output is correct
21 Correct 1985 ms 187792 KB Output is correct
22 Correct 1983 ms 187448 KB Output is correct
23 Correct 1292 ms 157052 KB Output is correct
24 Correct 430 ms 196736 KB Output is correct
25 Correct 1634 ms 157060 KB Output is correct
26 Correct 2040 ms 187120 KB Output is correct
27 Correct 4783 ms 159684 KB Output is correct
28 Correct 7021 ms 162776 KB Output is correct
29 Correct 8278 ms 186660 KB Output is correct
30 Correct 1494 ms 158764 KB Output is correct
31 Correct 8615 ms 195488 KB Output is correct
32 Execution timed out 9019 ms 194988 KB Time limit exceeded
33 Halted 0 ms 0 KB -