oj.uz

답안 #666228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
666228 2022-11-27T20:20:13 Z rainboy Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 129532 KB 
#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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 64972 KB Output is correct
2 Correct 36 ms 65020 KB Output is correct
3 Correct 39 ms 65024 KB Output is correct
4 Correct 26 ms 65044 KB Output is correct
5 Correct 34 ms 65028 KB Output is correct
6 Correct 31 ms 64980 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 9076 ms 129532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 64972 KB Output is correct
2 Correct 36 ms 65020 KB Output is correct
3 Correct 39 ms 65024 KB Output is correct
4 Correct 26 ms 65044 KB Output is correct
5 Correct 34 ms 65028 KB Output is correct
6 Correct 31 ms 64980 KB Output is correct
7 Execution timed out 9076 ms 129532 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 64972 KB Output is correct
2 Correct 36 ms 65020 KB Output is correct
3 Correct 39 ms 65024 KB Output is correct
4 Correct 26 ms 65044 KB Output is correct
5 Correct 34 ms 65028 KB Output is correct
6 Correct 31 ms 64980 KB Output is correct
7 Execution timed out 9076 ms 129532 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 64972 KB Output is correct
2 Correct 36 ms 65020 KB Output is correct
3 Correct 39 ms 65024 KB Output is correct
4 Correct 26 ms 65044 KB Output is correct
5 Correct 34 ms 65028 KB Output is correct
6 Correct 31 ms 64980 KB Output is correct
7 Execution timed out 9076 ms 129532 KB Time limit exceeded
8 Halted 0 ms 0 KB -