Submission #666228

#	Time	Username	Problem	Language	Result	Execution time	Memory
666228		rainboy	Escape Route (JOI21_escape_route)	C++17	5 / 100	9076 ms	129532 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]; char visited[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;
		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 i = ii[hh[h]];
		h_ = h;
		while (h_ < q && ii[hh[h_]] == i)
			h_++;
		for (int h1 = h; h1 < h_; h1++) {
			int h1_ = hh[h1], j = jj[h1_];
			long long r = rr[h1_];
			memset(dd, 0x3f, n * sizeof *dd), dd[i] = r;
			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 || dd[i_] > dd[i]))
						i_ = i;
				i = i_;
				visited[i] = 1;
				long long d = dd[i];
				for (int j = 0; j < n; j++)
					if (!visited[j] && ww[i][j] != INF)
						dd[j] = min(dd[j], (d % md <= cc[i][j] ? d : (d + md - 1) / md * md) + ww[i][j]);
			}
			ans[h1_] = dd[j] - r;
		}
	}
	return ans;
}

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