oj.uz

Submission #527558

# Submission time Handle Problem Language Result Execution time Memory
527558 2022-02-17T16:07:40 Z rainboy 도로 건설 사업 (JOI13_construction) C
40 / 100
 5000 ms 26032 KB 
#include <stdio.h>
#include <string.h>

#define N	200000
#define K	200000
#define M	(N * 2)

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 xx[N + K * 2], yy[N + K * 2], n, k;
int uu[M], vv[M], ww[M], m; long long ss[M];

int compare_xy(int i, int j) {
	return xx[i] != xx[j] ? xx[i] - xx[j] : yy[i] - yy[j];
}

int compare_w(int h1, int h2) {
	return ww[h1] - ww[h2];
}

int (*compare)(int, int);

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int ok(int x1, int x2, int y1, int y2) {
	int h;

	for (h = 0; h < k; h++) {
		int xl = max(xx[n + (h << 1 | 0)], x1), xr = min(xx[n + (h << 1 | 1)], x2);
		int yl = max(yy[n + (h << 1 | 0)], y1), yr = min(yy[n + (h << 1 | 1)], y2);

		if (xl <= xr && yl <= yr)
			return 0;
	}
	return 1;
}

int ds[N];

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

int join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

int main() {
	static int ii[N], hh[M];
	int m_, q, h, i, r, tmp;

	scanf("%d%d%d", &n, &k, &q);
	for (i = 0; i < n + k * 2; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (r = 0; r < 2; r++) {
		for (i = 0; i < n; i++)
			ii[i] = i;
		compare = compare_xy, sort(ii, 0, n);
		for (i = 0; i + 1 < n; i++)
			if (xx[ii[i]] == xx[ii[i + 1]] && ok(xx[ii[i]], xx[ii[i + 1]], yy[ii[i]], yy[ii[i + 1]]))
				uu[m] = ii[i], vv[m] = ii[i + 1], ww[m] = yy[ii[i + 1]] - yy[ii[i]], m++;
		for (i = 0; i < n + k * 2; i++)
			tmp = xx[i], xx[i] = yy[i], yy[i] = tmp;
	}
	for (h = 0; h < m; h++)
		hh[h] = h;
	compare = compare_w, sort(hh, 0, m);
	memset(ds, -1, n * sizeof *ds);
	m_ = 0;
	for (h = 0; h < m; h++)
		if (join(uu[hh[h]], vv[hh[h]]))
			hh[m_++] = hh[h];
	m = m_;
	for (h = 0; h < m; h++)
		ss[h] = (h == 0 ? 0 : ss[h - 1]) + ww[hh[h]];
	while (q--) {
		int w, c;

		scanf("%d%d", &w, &c);
		if (c < n - m)
			printf("-1\n");
		else {
			int lower, upper;

			lower = n - c - 1, upper = m;
			while (upper - lower > 1) {
				h = (lower + upper) / 2;
				if (ww[hh[h]] > w)
					upper = h;
				else
					lower = h;
			}
			printf("%lld\n", ss[lower] + (long long) (n - upper) * w);
		}
	}
	return 0;
}

Compilation message

construction.c: In function 'main':
construction.c:90:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%d%d%d", &n, &k, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.c:92:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.c:117:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   scanf("%d%d", &w, &c);
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 688 KB Output is correct
2 Correct 170 ms 5936 KB Output is correct
3 Correct 164 ms 6032 KB Output is correct
4 Correct 231 ms 11284 KB Output is correct
5 Correct 164 ms 8304 KB Output is correct
6 Correct 168 ms 6088 KB Output is correct
7 Correct 190 ms 11588 KB Output is correct
8 Correct 203 ms 8396 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 688 KB Output is correct
2 Correct 170 ms 5936 KB Output is correct
3 Correct 164 ms 6032 KB Output is correct
4 Correct 231 ms 11284 KB Output is correct
5 Correct 164 ms 8304 KB Output is correct
6 Correct 168 ms 6088 KB Output is correct
7 Correct 190 ms 11588 KB Output is correct
8 Correct 203 ms 8396 KB Output is correct
9 Correct 1323 ms 6820 KB Output is correct
10 Correct 1265 ms 6808 KB Output is correct
11 Correct 895 ms 6804 KB Output is correct
12 Correct 950 ms 6796 KB Output is correct
13 Execution timed out 5077 ms 6164 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 688 KB Output is correct
2 Correct 170 ms 5936 KB Output is correct
3 Correct 164 ms 6032 KB Output is correct
4 Correct 231 ms 11284 KB Output is correct
5 Correct 164 ms 8304 KB Output is correct
6 Correct 168 ms 6088 KB Output is correct
7 Correct 190 ms 11588 KB Output is correct
8 Correct 203 ms 8396 KB Output is correct
9 Correct 418 ms 13684 KB Output is correct
10 Correct 445 ms 12312 KB Output is correct
11 Correct 418 ms 14592 KB Output is correct
12 Correct 558 ms 22280 KB Output is correct
13 Correct 346 ms 19172 KB Output is correct
14 Correct 584 ms 26004 KB Output is correct
15 Correct 468 ms 24780 KB Output is correct
16 Correct 450 ms 23796 KB Output is correct
17 Correct 481 ms 26032 KB Output is correct
18 Correct 550 ms 22896 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 688 KB Output is correct
2 Correct 170 ms 5936 KB Output is correct
3 Correct 164 ms 6032 KB Output is correct
4 Correct 231 ms 11284 KB Output is correct
5 Correct 164 ms 8304 KB Output is correct
6 Correct 168 ms 6088 KB Output is correct
7 Correct 190 ms 11588 KB Output is correct
8 Correct 203 ms 8396 KB Output is correct
9 Correct 1323 ms 6820 KB Output is correct
10 Correct 1265 ms 6808 KB Output is correct
11 Correct 895 ms 6804 KB Output is correct
12 Correct 950 ms 6796 KB Output is correct
13 Execution timed out 5077 ms 6164 KB Time limit exceeded
14 Halted 0 ms 0 KB -