oj.uz

Submission #527556

# Submission time Handle Problem Language Result Execution time Memory
527556 2022-02-17T16:04:43 Z rainboy 도로 건설 사업 (JOI13_construction) C
10 / 100
 5000 ms 24728 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;

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;
	long long sum;

	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, sum = 0;
	for (h = 0; h < m; h++)
		if (join(uu[hh[h]], vv[hh[h]]))
			hh[m_++] = hh[h], sum += ww[hh[h]];
	m = m_;
	while (q--) {
		int w, c;

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

			ans = sum + (long long) (n - m) * w;
			for (h = m - 1; h >= n - c && ww[hh[h]] > w; h--)
				ans -= ww[hh[h]] - w;
			printf("%lld\n", ans);
		}
	}
	return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 448 KB Output is correct
2 Correct 168 ms 8856 KB Output is correct
3 Correct 166 ms 8768 KB Output is correct
4 Correct 228 ms 11268 KB Output is correct
5 Correct 169 ms 10296 KB Output is correct
6 Correct 173 ms 8904 KB Output is correct
7 Correct 158 ms 12812 KB Output is correct
8 Correct 201 ms 10440 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 448 KB Output is correct
2 Correct 168 ms 8856 KB Output is correct
3 Correct 166 ms 8768 KB Output is correct
4 Correct 228 ms 11268 KB Output is correct
5 Correct 169 ms 10296 KB Output is correct
6 Correct 173 ms 8904 KB Output is correct
7 Correct 158 ms 12812 KB Output is correct
8 Correct 201 ms 10440 KB Output is correct
9 Correct 1270 ms 18176 KB Output is correct
10 Correct 1234 ms 18176 KB Output is correct
11 Correct 866 ms 18216 KB Output is correct
12 Correct 906 ms 18204 KB Output is correct
13 Execution timed out 5004 ms 11776 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 448 KB Output is correct
2 Correct 168 ms 8856 KB Output is correct
3 Correct 166 ms 8768 KB Output is correct
4 Correct 228 ms 11268 KB Output is correct
5 Correct 169 ms 10296 KB Output is correct
6 Correct 173 ms 8904 KB Output is correct
7 Correct 158 ms 12812 KB Output is correct
8 Correct 201 ms 10440 KB Output is correct
9 Correct 4718 ms 24728 KB Output is correct
10 Correct 4816 ms 23284 KB Output is correct
11 Execution timed out 5048 ms 14228 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 448 KB Output is correct
2 Correct 168 ms 8856 KB Output is correct
3 Correct 166 ms 8768 KB Output is correct
4 Correct 228 ms 11268 KB Output is correct
5 Correct 169 ms 10296 KB Output is correct
6 Correct 173 ms 8904 KB Output is correct
7 Correct 158 ms 12812 KB Output is correct
8 Correct 201 ms 10440 KB Output is correct
9 Correct 1270 ms 18176 KB Output is correct
10 Correct 1234 ms 18176 KB Output is correct
11 Correct 866 ms 18216 KB Output is correct
12 Correct 906 ms 18204 KB Output is correct
13 Execution timed out 5004 ms 11776 KB Time limit exceeded
14 Halted 0 ms 0 KB -