Submission #666253

#	Time	Username	Problem	Language	Result	Execution time	Memory
666253		rainboy	Escape Route (JOI21_escape_route)	C++17	100 / 100	7370 ms	241676 KiB

escape_route

#include "escape_route.h"
#include <cstring>

using namespace std;

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

const int N = 90, M = N * (N - 1) / 2, Q = 3000000;
const long long INF = 0x3f3f3f3f3f3f3f3f;

typedef vector<int> vi;
typedef vector<long long> vl;

unsigned int X;

int rand_() {
	return (X *= 3) >> 1;
}

int ii[Q], jj[Q], hh[Q]; long long rr[Q];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
		while (j < k) {
			int c = ii[hh[j]] != ii[h] ? ii[hh[j]] - ii[h] : (rr[hh[j]] == rr[h] ? 0 : rr[hh[j]] < rr[h] ? -1 : 1);
			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

long long ww[N][N], cc[N][N], dd1[N][N], dd2[N][N], dd[N]; int pp[N], qu[N]; char visited[N], update[N];

vl calculate_necessary_time(int n, int m, long long md, int q, vi uu_, vi vv_, vl ww_, vl cc_, vi ii_, vi jj_, vl rr_) {
	for (int i = 0; i < n; i++)
		memset(ww[i], 0x3f, n * sizeof *ww[i]);
	for (int h = 0; h < m; h++) {
		int u = uu_[h], v = vv_[h];
		ww[u][v] = ww[v][u] = ww_[h], cc[u][v] = cc[v][u] = cc_[h] - ww_[h];
	}
	for (int t = 0; t < n; t++) {
		memset(dd1[t], -1, n * sizeof *dd1[t]), dd1[t][t] = md;
		memset(visited, 0, n * sizeof *visited);
		for (int h = 0; h < n; h++) {
			int j, j_ = -1;
			for (j = 0; j < n; j++)
				if (!visited[j] && (j_ == -1 || dd1[t][j_] < dd1[t][j]))
					j_ = j;
			j = j_;
			visited[j] = 1;
			long long d = dd1[t][j];
			for (int i = 0; i < n; i++)
				if (!visited[i] && ww[i][j] != INF)
					dd1[t][i] = max(dd1[t][i], min(d - ww[i][j], cc[i][j]));
		}
	}
	for (int s = 0; s < n; s++) {
		memset(dd2[s], 0x3f, n * sizeof *dd2[s]), dd2[s][s] = 0;
		memset(visited, 0, n * sizeof *visited);
		for (int h = 0; h < n; h++) {
			int i, i_ = -1;
			for (i = 0; i < n; i++)
				if (!visited[i] && (i_ == -1 || dd2[s][i_] > dd2[s][i]))
					i_ = i;
			i = i_;
			visited[i] = 1;
			long long d = dd2[s][i];
			for (int j = 0; j < n; j++)
				if (!visited[j] && ww[i][j] != INF)
					dd2[s][j] = min(dd2[s][j], (d % md <= cc[i][j] ? d : (d + md - 1) / md * md) + ww[i][j]);
		}
	}
	for (int h = 0; h < q; h++)
		ii[h] = ii_[h], jj[h] = jj_[h], rr[h] = rr_[h];
	for (int h = 0; h < q; h++)
		hh[h] = h;
	sort(hh, 0, q);
	vl ans(q);
	for (int h = 0, h_; h < q; h = h_) {
		int s = ii[hh[h]];
		h_ = h;
		while (h_ < q && ii[hh[h_]] == s)
			h_++;
		for (int i = 0; i < n; i++)
			qu[i] = i;
		for (int h1 = h; h1 < h_; h1++) {
			int h1_ = hh[h1], t = jj[h1_];
			long long r = rr[h1_];
			int upd = h1 == h;
			for (int i = 0; i < n; i++)
				if (pp[i] != -1 && dd[pp[i]] > cc[pp[i]][i] - r) {
					upd = 1;
					break;
				}
			if (upd) {
				for (int g = 0; g < n; g++) {
					int i = qu[g];
					update[i] = h1 == h || pp[i] != -1 && (update[pp[i]] || dd[pp[i]] > cc[pp[i]][i] - r);
				}
				int m = 0;
				for (int g = 0; g < n; g++) {
					int i = qu[g], tmp;
					if (!update[i])
						tmp = qu[g], qu[g] = qu[m], qu[m] = tmp, m++;
					else
						dd[i] = INF, pp[i] = -1;
				}
				dd[s] = 0;
				for (int g = 0; g < m; g++) {
					int i = qu[g];
					long long d = dd[i], d_;
					for (int g_ = m; g_ < n; g_++) {
						int j = qu[g_];
						if (ww[i][j] != INF && d <= cc[i][j] - r && dd[j] > (d_ = d + ww[i][j]))
							dd[j] = d_, pp[j] = i;
					}
				}
				for (int g = m; g < n; g++) {
					int tmp;
					for (int g_ = g + 1; g_ < n; g_++)
						if (dd[qu[g]] > dd[qu[g_]])
							tmp = qu[g], qu[g] = qu[g_], qu[g_] = tmp;
					int i = qu[g];
					long long d = dd[i], d_;
					for (int g_ = m + 1; g_ < n; g_++) {
						int j = qu[g_];
						if (ww[i][j] != INF && d <= cc[i][j] - r && dd[j] > (d_ = d + ww[i][j]))
							dd[j] = d_, pp[j] = i;
					}
				}
			}
			ans[h1_] = dd[t];
			for (int k = 0; k < n; k++)
				if (dd1[k][s] >= r && dd2[k][t] != INF)
					ans[h1_] = min(ans[h1_], md - r + dd2[k][t]);
		}
	}
	return ans;
}

Compilation message (stderr)

escape_route.cpp: In function 'vl calculate_necessary_time(int, int, long long int, int, vi, vi, vl, vl, vi, vi, vl)':
escape_route.cpp:109:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  109 |      update[i] = h1 == h || pp[i] != -1 && (update[pp[i]] || dd[pp[i]] > cc[pp[i]][i] - r);
      |                             ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 30 / 30