Submission #387027

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
387027	2021-04-07T20:03:53 Z	rainboy	Swapping Cities (APIO20_swap)	C++11	13 / 100	191 ms	8272 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	1 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	2 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	2 ms	364 KB	Output is correct
9	Correct	45 ms	3948 KB	Output is correct
10	Correct	54 ms	4844 KB	Output is correct
11	Correct	53 ms	4716 KB	Output is correct
12	Correct	59 ms	5100 KB	Output is correct
13	Correct	70 ms	4972 KB	Output is correct
14	Correct	53 ms	4204 KB	Output is correct
15	Correct	144 ms	6760 KB	Output is correct
16	Correct	141 ms	6680 KB	Output is correct
17	Correct	149 ms	6864 KB	Output is correct
18	Correct	125 ms	6864 KB	Output is correct
19	Correct	74 ms	4532 KB	Output is correct
20	Correct	137 ms	7784 KB	Output is correct
21	Correct	191 ms	7972 KB	Output is correct
22	Correct	147 ms	8272 KB	Output is correct
23	Correct	129 ms	8148 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	121 ms	7824 KB	Output is correct
4	Correct	169 ms	7888 KB	Output is correct
5	Correct	121 ms	8048 KB	Output is correct
6	Correct	150 ms	7888 KB	Output is correct
7	Correct	123 ms	8040 KB	Output is correct
8	Correct	120 ms	7832 KB	Output is correct
9	Correct	122 ms	7912 KB	Output is correct
10	Correct	130 ms	7844 KB	Output is correct

Subtask #3
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	2 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	2 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Incorrect	1 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	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	2 ms	364 KB	Output is correct
6	Correct	1 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	2 ms	364 KB	Output is correct
10	Correct	45 ms	3948 KB	Output is correct
11	Correct	54 ms	4844 KB	Output is correct
12	Correct	53 ms	4716 KB	Output is correct
13	Correct	59 ms	5100 KB	Output is correct
14	Correct	70 ms	4972 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Incorrect	1 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	1 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	2 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	2 ms	364 KB	Output is correct
9	Correct	45 ms	3948 KB	Output is correct
10	Correct	54 ms	4844 KB	Output is correct
11	Correct	53 ms	4716 KB	Output is correct
12	Correct	59 ms	5100 KB	Output is correct
13	Correct	70 ms	4972 KB	Output is correct
14	Correct	53 ms	4204 KB	Output is correct
15	Correct	144 ms	6760 KB	Output is correct
16	Correct	141 ms	6680 KB	Output is correct
17	Correct	149 ms	6864 KB	Output is correct
18	Correct	125 ms	6864 KB	Output is correct
19	Correct	121 ms	7824 KB	Output is correct
20	Correct	169 ms	7888 KB	Output is correct
21	Correct	121 ms	8048 KB	Output is correct
22	Correct	150 ms	7888 KB	Output is correct
23	Correct	123 ms	8040 KB	Output is correct
24	Correct	120 ms	7832 KB	Output is correct
25	Correct	122 ms	7912 KB	Output is correct
26	Correct	130 ms	7844 KB	Output is correct
27	Correct	1 ms	364 KB	Output is correct
28	Incorrect	1 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	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	2 ms	364 KB	Output is correct
6	Correct	1 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	2 ms	364 KB	Output is correct
10	Correct	45 ms	3948 KB	Output is correct
11	Correct	54 ms	4844 KB	Output is correct
12	Correct	53 ms	4716 KB	Output is correct
13	Correct	59 ms	5100 KB	Output is correct
14	Correct	70 ms	4972 KB	Output is correct
15	Correct	53 ms	4204 KB	Output is correct
16	Correct	144 ms	6760 KB	Output is correct
17	Correct	141 ms	6680 KB	Output is correct
18	Correct	149 ms	6864 KB	Output is correct
19	Correct	125 ms	6864 KB	Output is correct
20	Correct	121 ms	7824 KB	Output is correct
21	Correct	169 ms	7888 KB	Output is correct
22	Correct	121 ms	8048 KB	Output is correct
23	Correct	150 ms	7888 KB	Output is correct
24	Correct	123 ms	8040 KB	Output is correct
25	Correct	120 ms	7832 KB	Output is correct
26	Correct	122 ms	7912 KB	Output is correct
27	Correct	130 ms	7844 KB	Output is correct
28	Correct	1 ms	364 KB	Output is correct
29	Incorrect	1 ms	364 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Submission #387027

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