Submission #962001

#	Time	Username	Problem	Language	Result	Execution time	Memory
962001		Pring	Escape Route (JOI21_escape_route)	C++17	100 / 100	4704 ms	783340 KiB

escape_route

#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 (stderr)

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 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 30 / 30