oj.uz

Submission #758443

# Submission time Handle Problem Language Result Execution time Memory
758443 2023-06-14T15:52:13 Z rainboy Cyberland (APIO23_cyberland) C++17
100 / 100
 2363 ms 14008 KB 
#include "cyberland.h"
#include <cstdlib>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 100000, K = 120;
const double INF = 1e18;

int *ej[N], *ew[N], eo[N];

void append(int i, int j, int w) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0) {
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
		ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
	}
	ej[i][o] = j, ew[i][o] = w;
}

double dd[N], dd_[N]; int iq[N + 1], pq[N], cnt;

int lt(int i, int j) { return dd[i] < dd[j]; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;
	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;
	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add_last(int i) {
	iq[pq[i] = ++cnt] = i;
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];
	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

void dijkstra(int n) {
	for (int i = 0; i < n; i++)
		pq_add_last(i);
	for (int h = cnt / 2; h > 0; h--)
		pq_dn(iq[h]);
	while (cnt) {
		int i = pq_remove_first();
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o], w = ew[i][o];
			double d = dd[i] + w;
			if (dd[j] > d)
				dd[j] = d, pq_up(j);
		}
	}
}

double solve(int n, int m, int k, int t, vi ii, vi jj, vi ww, vi type) {
	type[0] = 0;
	for (int i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		ew[i] = (int *) malloc(2 * sizeof *ew[i]);
		eo[i] = 0;
	}
	for (int h = 0; h < m; h++) {
		int i = ii[h], j = jj[h], w = ww[h];
		if (i != t)
			append(i, j, w);
		if (j != t)
			append(j, i, w);
	}
	for (int i = 0; i < n; i++)
		dd[i] = INF;
	dd[0] = 0;
	dijkstra(n);
	for (int i = 0; i < n; i++)
		dd[i] = type[i] == 0 && dd[i] != INF ? 0 : INF;
	dijkstra(n);
	k = min(k, K);
	while (k--) {
		for (int i = 0; i < n; i++)
			dd_[i] = dd[i];
		for (int i = 0; i < n; i++)
			if (type[i] == 2)
				dd[i] = INF;
		for (int i = 0; i < n; i++)
			if (type[i] == 2 && dd_[i] != INF)
				for (int o = eo[i]; o--; ) {
					int j = ej[i][o], w = ew[i][o];
					dd[j] = min(dd[j], dd_[i] / 2 + w);
				}
		dijkstra(n);
	}
	return dd[t] == INF ? -1 : dd[t];
}

Compilation message

cyberland.cpp: In function 'void append(int, int, int)':
cyberland.cpp:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1996 KB Correct.
2 Correct 37 ms 2004 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 3320 KB Correct.
2 Correct 220 ms 3852 KB Correct.
3 Correct 202 ms 3652 KB Correct.
4 Correct 215 ms 3724 KB Correct.
5 Correct 215 ms 3868 KB Correct.
6 Correct 239 ms 3460 KB Correct.
7 Correct 309 ms 4376 KB Correct.
8 Correct 165 ms 3068 KB Correct.
9 Correct 133 ms 3568 KB Correct.
10 Correct 128 ms 3548 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 3600 KB Correct.
2 Correct 184 ms 3668 KB Correct.
3 Correct 167 ms 3396 KB Correct.
4 Correct 134 ms 3688 KB Correct.
5 Correct 134 ms 3584 KB Correct.
6 Correct 46 ms 1364 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 8272 KB Correct.
2 Correct 147 ms 3624 KB Correct.
3 Correct 131 ms 3476 KB Correct.
4 Correct 136 ms 3440 KB Correct.
5 Correct 100 ms 3532 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 3676 KB Correct.
2 Correct 126 ms 4040 KB Correct.
3 Correct 130 ms 3788 KB Correct.
4 Correct 143 ms 3660 KB Correct.
5 Correct 88 ms 3700 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 3856 KB Correct.
2 Correct 107 ms 3500 KB Correct.
3 Correct 121 ms 10980 KB Correct.
4 Correct 90 ms 3420 KB Correct.
5 Correct 98 ms 3716 KB Correct.
6 Correct 118 ms 3636 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 3500 KB Correct.
2 Correct 15 ms 724 KB Correct.
3 Correct 725 ms 13800 KB Correct.
4 Correct 399 ms 8188 KB Correct.
5 Correct 342 ms 7104 KB Correct.
6 Correct 108 ms 4816 KB Correct.
7 Correct 385 ms 7948 KB Correct.
8 Correct 285 ms 6836 KB Correct.
9 Correct 117 ms 3668 KB Correct.
10 Correct 120 ms 3636 KB Correct.
11 Correct 246 ms 7004 KB Correct.
12 Correct 139 ms 4084 KB Correct.
13 Correct 128 ms 3788 KB Correct.
14 Correct 359 ms 8672 KB Correct.
15 Correct 310 ms 6840 KB Correct.
16 Correct 125 ms 3744 KB Correct.
17 Correct 146 ms 3960 KB Correct.
18 Correct 141 ms 3876 KB Correct.
19 Correct 384 ms 6756 KB Correct.
20 Correct 9 ms 596 KB Correct.
21 Correct 11 ms 700 KB Correct.
22 Correct 8 ms 724 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 3576 KB Correct.
2 Correct 46 ms 716 KB Correct.
3 Correct 1989 ms 14008 KB Correct.
4 Correct 469 ms 6840 KB Correct.
5 Correct 1255 ms 7008 KB Correct.
6 Correct 342 ms 4864 KB Correct.
7 Correct 816 ms 8436 KB Correct.
8 Correct 438 ms 7116 KB Correct.
9 Correct 381 ms 3620 KB Correct.
10 Correct 383 ms 3652 KB Correct.
11 Correct 188 ms 6208 KB Correct.
12 Correct 424 ms 4020 KB Correct.
13 Correct 388 ms 3700 KB Correct.
14 Correct 1520 ms 7352 KB Correct.
15 Correct 2363 ms 9108 KB Correct.
16 Correct 631 ms 7372 KB Correct.
17 Correct 476 ms 6964 KB Correct.
18 Correct 395 ms 3840 KB Correct.
19 Correct 460 ms 4080 KB Correct.
20 Correct 430 ms 3788 KB Correct.
21 Correct 1228 ms 7080 KB Correct.
22 Correct 26 ms 596 KB Correct.
23 Correct 36 ms 616 KB Correct.
24 Correct 21 ms 724 KB Correct.