Submission #387026

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
387026	2021-04-07T20:03:43 Z	rainboy	Swapping Cities (APIO20_swap)	C++11	13 / 100	160 ms	9040 KB

swap

#include "swap.h"
#include <cstring>
#include <vector>

const int N = 100000, M = 200000, INF = 0x3f3f3f3f;

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

unsigned int X = 12345;

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

int ww[M];

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)
			if (ww[hh[j]] == ww[h])
				j++;
			else if (ww[hh[j]] < ww[h]) {
				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;
	}
}

int ds[N], ww_[N], ww1[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j, int w, int special) {
	i = find(i);
	j = find(j);
	if (i == j) {
		ww1[i] = min(ww1[i], w);
		return;
	}
	if (ds[i] > ds[j]) {
		ds[i] = j, ww_[i] = w;
		if (special)
			ww1[j] = min(ww1[j], w);
	} else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, ww_[j] = w;
		if (special)
			ww1[i] = min(ww1[i], w);
	}
}

int n, m;

void init(int n_, int m_, std::vector<int> ii, std::vector<int> jj, std::vector<int> WW) {
	static int hh[M], dd[N];
	int h;

	n = n_, m = m_;
	for (h = 0; h < m; h++)
		ww[h] = WW[h], hh[h] = h;
	sort(hh, 0, m);
	memset(dd, 0, n * sizeof *dd);
	memset(ds, -1, n * sizeof *ds);
	memset(ww_, 0x3f, n * sizeof *ww_);
	memset(ww1, 0x3f, n * sizeof *ww1);
	for (h = 0; h < m; h++) {
		int i = ii[hh[h]], j = jj[hh[h]], w = ww[hh[h]];

		dd[i]++, dd[j]++;
		join(i, j, w, dd[i] > 2 || dd[j] > 2);
	}
}

int getMinimumFuelCapacity(int i, int j) {
	long long w1 = 0, w2 = INF;

	while (i != j)
		if (ww_[i] < ww_[j])
			w1 = max(w1, ww_[i]), w2 = min(w2, ww1[i]), i = ds[i];
		else
			w1 = max(w1, ww_[j]), w2 = min(w2, ww1[j]), j = ds[j];
	while (i >= 0) {
		if (ww1[i] != INF) {
			w2 = min(w2, ww1[i]);
			break;
		}
		i = ds[i];
	}
	return w2 == INF ? -1 : max(w1, w2);
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	2 ms	364 KB	Output is correct
9	Correct	46 ms	4460 KB	Output is correct
10	Correct	56 ms	5356 KB	Output is correct
11	Correct	54 ms	5228 KB	Output is correct
12	Correct	58 ms	5632 KB	Output is correct
13	Correct	58 ms	5484 KB	Output is correct
14	Correct	53 ms	4716 KB	Output is correct
15	Correct	146 ms	7156 KB	Output is correct
16	Correct	140 ms	7068 KB	Output is correct
17	Correct	149 ms	7376 KB	Output is correct
18	Correct	127 ms	7380 KB	Output is correct
19	Correct	74 ms	5044 KB	Output is correct
20	Correct	158 ms	8296 KB	Output is correct
21	Correct	143 ms	8488 KB	Output is correct
22	Correct	160 ms	9040 KB	Output is correct
23	Correct	130 ms	8656 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	130 ms	8464 KB	Output is correct
4	Correct	117 ms	8528 KB	Output is correct
5	Correct	126 ms	8704 KB	Output is correct
6	Correct	118 ms	8400 KB	Output is correct
7	Correct	120 ms	8684 KB	Output is correct
8	Correct	119 ms	8472 KB	Output is correct
9	Correct	121 ms	8552 KB	Output is correct
10	Correct	127 ms	8488 KB	Output is correct

Subtask #3
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	2 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	2 ms	364 KB	Output is correct
11	Incorrect	2 ms	364 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	2 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	2 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	2 ms	364 KB	Output is correct
10	Correct	46 ms	4460 KB	Output is correct
11	Correct	56 ms	5356 KB	Output is correct
12	Correct	54 ms	5228 KB	Output is correct
13	Correct	58 ms	5632 KB	Output is correct
14	Correct	58 ms	5484 KB	Output is correct
15	Correct	2 ms	364 KB	Output is correct
16	Incorrect	2 ms	364 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	2 ms	364 KB	Output is correct
9	Correct	46 ms	4460 KB	Output is correct
10	Correct	56 ms	5356 KB	Output is correct
11	Correct	54 ms	5228 KB	Output is correct
12	Correct	58 ms	5632 KB	Output is correct
13	Correct	58 ms	5484 KB	Output is correct
14	Correct	53 ms	4716 KB	Output is correct
15	Correct	146 ms	7156 KB	Output is correct
16	Correct	140 ms	7068 KB	Output is correct
17	Correct	149 ms	7376 KB	Output is correct
18	Correct	127 ms	7380 KB	Output is correct
19	Correct	130 ms	8464 KB	Output is correct
20	Correct	117 ms	8528 KB	Output is correct
21	Correct	126 ms	8704 KB	Output is correct
22	Correct	118 ms	8400 KB	Output is correct
23	Correct	120 ms	8684 KB	Output is correct
24	Correct	119 ms	8472 KB	Output is correct
25	Correct	121 ms	8552 KB	Output is correct
26	Correct	127 ms	8488 KB	Output is correct
27	Correct	2 ms	364 KB	Output is correct
28	Incorrect	2 ms	364 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	2 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	2 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	2 ms	364 KB	Output is correct
10	Correct	46 ms	4460 KB	Output is correct
11	Correct	56 ms	5356 KB	Output is correct
12	Correct	54 ms	5228 KB	Output is correct
13	Correct	58 ms	5632 KB	Output is correct
14	Correct	58 ms	5484 KB	Output is correct
15	Correct	53 ms	4716 KB	Output is correct
16	Correct	146 ms	7156 KB	Output is correct
17	Correct	140 ms	7068 KB	Output is correct
18	Correct	149 ms	7376 KB	Output is correct
19	Correct	127 ms	7380 KB	Output is correct
20	Correct	130 ms	8464 KB	Output is correct
21	Correct	117 ms	8528 KB	Output is correct
22	Correct	126 ms	8704 KB	Output is correct
23	Correct	118 ms	8400 KB	Output is correct
24	Correct	120 ms	8684 KB	Output is correct
25	Correct	119 ms	8472 KB	Output is correct
26	Correct	121 ms	8552 KB	Output is correct
27	Correct	127 ms	8488 KB	Output is correct
28	Correct	2 ms	364 KB	Output is correct
29	Incorrect	2 ms	364 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Submission #387026

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 17.0

Subtask #4 0 / 20.0

Subtask #5 0 / 23.0

Subtask #6 0 / 27.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 17.0

Subtask #4
0 / 20.0

Subtask #5
0 / 23.0

Subtask #6
0 / 27.0