oj.uz

Submission #962001

# Submission time Handle Problem Language Result Execution time Memory
962001 2024-04-13T02:24:27 Z Pring Escape Route (JOI21_escape_route) C++17
100 / 100
 4704 ms 783340 KB 
#include <bits/stdc++.h>
#include "escape_route.h"
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

namespace {
	const int MXN = 95;
	const ll INF = 3.9e18;
	int n, m, q;
	ll s;
	vector<int> eu, ev, qu, qv;
	vector<ll> elt, ect, qt;
	vector<ll> ans;
	ll el[MXN][MXN], ec[MXN][MXN];

	ll dis[MXN][MXN];
	ll dp[MXN][MXN][MXN];

	namespace SPFA {
		vector<pli> rnk[MXN];
		struct CPU {
			deque<pair<ll, vector<ll>>> dq;
			deque<pli> num;
			int ptr[MXN], span[MXN];
			vector<ll> a;
			ll init(int sr) {
				a.resize(n, INF);
				a[sr] = 0;
				fill(ptr, ptr + n, 0);
				dq.push_back(mp(s, a));
				return rnk[sr][0].fs;
			}
			vector<ll> GET(ll t) {
				return lower_bound(dq.begin(), dq.end(), mp(t, vector<ll>())) -> sc;
			}
			void TIDY() {
				vector<pii> v(n);
				FOR(i, 0, n) v[i] = mp(0, i);
				for (auto [t, w] : dq) {
					int cnt = n;
					FOR(i, 0, n) if (w[i] >= INF) {
						v[i].fs++;
						cnt--;
					}
					num.push_back(mp(t, cnt));
				}
				sort(v.begin(), v.end());
				FOR(i, 0, n) span[i] = v[i].sc;
			}
		} cpu[MXN];
		ll time[MXN];

		void GET_RNK(int id) {
			vector<pli> &dist = rnk[id];
			FOR(i, 0, n + 1) dist.push_back(mp(ec[id][i] - el[id][i], i));
			sort(dist.begin(), dist.end(), greater<pli>());
		}
		void PRE() {
			FOR(i, 0, n) GET_RNK(i);
			FOR(i, 0, n) time[i] = cpu[i].init(i);
		}
		void RELAX(int id, ll t) {
			while (true) {
				ll big = -INF;
				bool found = false;
				FOR(i, 0, n) {
					int &e = cpu[id].ptr[i];
					ll len = cpu[id].a[i];
					if (t + len <= rnk[i][e].fs) {
						int j = rnk[i][e].sc;
						vector<ll> d = cpu[j].GET(t + len + el[i][j]);
						FOR(k, 0, n) cpu[id].a[k] = min(cpu[id].a[k], len + el[i][j] + d[k]);
						found = true;
						e++;
						break;
					}
					big = max(big, rnk[i][e].fs - cpu[id].a[i]);
				}
				if (found) continue;
				time[id] = big;
				debug(big);
				break;
			}
			cpu[id].dq.push_front(mp(t, cpu[id].a));
		}
		void DO() {
			PRE();
			while (true) {
				auto it = max_element(time, time + n);
				if (*it < 0) break;
				RELAX(it - time, *it);
			}
			FOR(i, 0, n) cpu[i].TIDY();
			/*
			FOR(i, 0, n) {
				cout << i << ": " << endl;
				FOR(j, 0, n) cout << cpu[i].span[j] << ' ';
				cout << endl << endl;
			}
			*/
		}
	}

	void DIJKSTRA(int sr, ll *dis) {
		bitset<MXN> b;
		fill(dis, dis + n, INF);
		dis[sr] = 0;
		b.reset();
		FOR($, 0, n) {
			int id = -1;
			FOR(i, 0, n) {
				if (b[i]) continue;
				if (id == -1 || dis[i] < dis[id]) id = i;
			}
			b[id] = true;
			ll t = dis[id] % s, day = dis[id] / s;
			FOR(i, 0, n) {
				if (b[i]) continue;
				if (t + el[id][i] <= ec[id][i]) {
					dis[i] = min(dis[i], dis[id] + el[id][i]);
				} else {
					dis[i] = min(dis[i], s * (day + 1) + el[id][i]);
				}
				if (sr == 4) debug(id, i, dis[i]);
			}
		}
	}
	void PRE() {
		SPFA::DO();
		FOR(i, 0, n) DIJKSTRA(i, dis[i]);
		FOR(id, 0, n) {
			fill(dp[id][0], dp[id][0] + n, INF);
			FOR(j, 0, n) {
				int y = SPFA::cpu[id].span[j];
				FOR(k, 0, n) {
					dp[id][j + 1][k] = min(dp[id][j][k], dis[y][k]);
				}
			}
		}
	}
	ll query(int u, int v, ll t) {
		debug(u, v, t);
		vector<ll> w = SPFA::cpu[u].GET(t);
		// for (auto &i : w) cout << i << ' ';
		// cout << endl;
		if (w[v] != INF) return w[v];
		int x = lower_bound(SPFA::cpu[u].num.begin(), SPFA::cpu[u].num.end(), mp(t, 0)) -> sc;
		return s - t + dp[u][x][v];
	}

	vector<ll> solve() {
		FOR(i, 0, n) FOR(j, 0, n + 1) {
			el[i][j] = INF;
			ec[i][j] = 0;
		}
		FOR(i, 0, m) {
			el[eu[i]][ev[i]] = elt[i];
			ec[eu[i]][ev[i]] = ect[i];
			el[ev[i]][eu[i]] = elt[i];
			ec[ev[i]][eu[i]] = ect[i];
		}
		PRE();
		FOR(i, 0, q) ans.push_back(query(qu[i], qv[i], qt[i]));
		// FOR(i, 0, n) cout << dis[4][i] << ' ';
		// cout << endl;
		return ans;
	}
}

vector<ll> calculate_necessary_time(int N, int M, ll S, int Q, vector<int> A, vector<int> B, vector<ll> L, vector<ll> C, vector<int> U, vector<int> V, vector<ll> T) {
	::n = N;
	::m = M;
	::s = S;
	::q = Q;
	::eu = A;
	::ev = B;
	::elt = L;
	::ect = C;
	::qu = U;
	::qv = V;
	::qt = T;
	return solve();
}

Compilation message

escape_route.cpp: In function 'void {anonymous}::SPFA::RELAX(int, ll)':
escape_route.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 39
      |                    ^~
escape_route.cpp:100:5: note: in expansion of macro 'debug'
  100 |     debug(big);
      |     ^~~~~
escape_route.cpp: In function 'void {anonymous}::DIJKSTRA(int, ll*)':
escape_route.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 39
      |                    ^~
escape_route.cpp:143:18: note: in expansion of macro 'debug'
  143 |     if (sr == 4) debug(id, i, dis[i]);
      |                  ^~~~~
escape_route.cpp: In function 'll {anonymous}::query(int, int, ll)':
escape_route.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 39
      |                    ^~
escape_route.cpp:161:3: note: in expansion of macro 'debug'
  161 |   debug(u, v, t);
      |   ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 65368 KB Output is correct
2 Correct 14 ms 65372 KB Output is correct
3 Correct 50 ms 65328 KB Output is correct
4 Correct 10 ms 65372 KB Output is correct
5 Correct 11 ms 65372 KB Output is correct
6 Correct 10 ms 65372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 201644 KB Output is correct
2 Correct 509 ms 269756 KB Output is correct
3 Correct 606 ms 249684 KB Output is correct
4 Correct 696 ms 278952 KB Output is correct
5 Correct 639 ms 278704 KB Output is correct
6 Correct 9 ms 65372 KB Output is correct
7 Correct 579 ms 249616 KB Output is correct
8 Correct 392 ms 270604 KB Output is correct
9 Correct 568 ms 239664 KB Output is correct
10 Correct 685 ms 279380 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 65368 KB Output is correct
2 Correct 14 ms 65372 KB Output is correct
3 Correct 50 ms 65328 KB Output is correct
4 Correct 10 ms 65372 KB Output is correct
5 Correct 11 ms 65372 KB Output is correct
6 Correct 10 ms 65372 KB Output is correct
7 Correct 603 ms 201644 KB Output is correct
8 Correct 509 ms 269756 KB Output is correct
9 Correct 606 ms 249684 KB Output is correct
10 Correct 696 ms 278952 KB Output is correct
11 Correct 639 ms 278704 KB Output is correct
12 Correct 9 ms 65372 KB Output is correct
13 Correct 579 ms 249616 KB Output is correct
14 Correct 392 ms 270604 KB Output is correct
15 Correct 568 ms 239664 KB Output is correct
16 Correct 685 ms 279380 KB Output is correct
17 Correct 1112 ms 251728 KB Output is correct
18 Correct 921 ms 247080 KB Output is correct
19 Correct 687 ms 272820 KB Output is correct
20 Correct 1169 ms 253136 KB Output is correct
21 Correct 1089 ms 283396 KB Output is correct
22 Correct 1055 ms 282672 KB Output is correct
23 Correct 1164 ms 253024 KB Output is correct
24 Correct 428 ms 271900 KB Output is correct
25 Correct 1014 ms 241072 KB Output is correct
26 Correct 1134 ms 282900 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 65368 KB Output is correct
2 Correct 14 ms 65372 KB Output is correct
3 Correct 50 ms 65328 KB Output is correct
4 Correct 10 ms 65372 KB Output is correct
5 Correct 11 ms 65372 KB Output is correct
6 Correct 10 ms 65372 KB Output is correct
7 Correct 603 ms 201644 KB Output is correct
8 Correct 509 ms 269756 KB Output is correct
9 Correct 606 ms 249684 KB Output is correct
10 Correct 696 ms 278952 KB Output is correct
11 Correct 639 ms 278704 KB Output is correct
12 Correct 9 ms 65372 KB Output is correct
13 Correct 579 ms 249616 KB Output is correct
14 Correct 392 ms 270604 KB Output is correct
15 Correct 568 ms 239664 KB Output is correct
16 Correct 685 ms 279380 KB Output is correct
17 Correct 1112 ms 251728 KB Output is correct
18 Correct 921 ms 247080 KB Output is correct
19 Correct 687 ms 272820 KB Output is correct
20 Correct 1169 ms 253136 KB Output is correct
21 Correct 1089 ms 283396 KB Output is correct
22 Correct 1055 ms 282672 KB Output is correct
23 Correct 1164 ms 253024 KB Output is correct
24 Correct 428 ms 271900 KB Output is correct
25 Correct 1014 ms 241072 KB Output is correct
26 Correct 1134 ms 282900 KB Output is correct
27 Correct 1939 ms 340456 KB Output is correct
28 Correct 1736 ms 323248 KB Output is correct
29 Correct 987 ms 359444 KB Output is correct
30 Correct 2188 ms 334680 KB Output is correct
31 Correct 1952 ms 367472 KB Output is correct
32 Correct 1875 ms 368632 KB Output is correct
33 Correct 417 ms 274712 KB Output is correct
34 Correct 2066 ms 331876 KB Output is correct
35 Correct 2063 ms 369672 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 65368 KB Output is correct
2 Correct 14 ms 65372 KB Output is correct
3 Correct 50 ms 65328 KB Output is correct
4 Correct 10 ms 65372 KB Output is correct
5 Correct 11 ms 65372 KB Output is correct
6 Correct 10 ms 65372 KB Output is correct
7 Correct 603 ms 201644 KB Output is correct
8 Correct 509 ms 269756 KB Output is correct
9 Correct 606 ms 249684 KB Output is correct
10 Correct 696 ms 278952 KB Output is correct
11 Correct 639 ms 278704 KB Output is correct
12 Correct 9 ms 65372 KB Output is correct
13 Correct 579 ms 249616 KB Output is correct
14 Correct 392 ms 270604 KB Output is correct
15 Correct 568 ms 239664 KB Output is correct
16 Correct 685 ms 279380 KB Output is correct
17 Correct 1112 ms 251728 KB Output is correct
18 Correct 921 ms 247080 KB Output is correct
19 Correct 687 ms 272820 KB Output is correct
20 Correct 1169 ms 253136 KB Output is correct
21 Correct 1089 ms 283396 KB Output is correct
22 Correct 1055 ms 282672 KB Output is correct
23 Correct 1164 ms 253024 KB Output is correct
24 Correct 428 ms 271900 KB Output is correct
25 Correct 1014 ms 241072 KB Output is correct
26 Correct 1134 ms 282900 KB Output is correct
27 Correct 1939 ms 340456 KB Output is correct
28 Correct 1736 ms 323248 KB Output is correct
29 Correct 987 ms 359444 KB Output is correct
30 Correct 2188 ms 334680 KB Output is correct
31 Correct 1952 ms 367472 KB Output is correct
32 Correct 1875 ms 368632 KB Output is correct
33 Correct 417 ms 274712 KB Output is correct
34 Correct 2066 ms 331876 KB Output is correct
35 Correct 2063 ms 369672 KB Output is correct
36 Correct 4006 ms 772048 KB Output is correct
37 Correct 3754 ms 667112 KB Output is correct
38 Correct 4449 ms 742404 KB Output is correct
39 Correct 4704 ms 783340 KB Output is correct
40 Correct 4545 ms 782716 KB Output is correct
41 Correct 446 ms 276004 KB Output is correct
42 Correct 4386 ms 759428 KB Output is correct
43 Correct 3718 ms 659924 KB Output is correct