oj.uz

답안 #532358

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
532358 2022-03-02T18:30:15 Z rainboy 절취선 (JOI14_ho_t5) C
10 / 100
 9 ms 592 KB 
#include <stdio.h>
#include <string.h>

#define N	1004

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

int ds[N];

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

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

int intersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
	int tmp;

	if (x1 > x2)
		tmp = x1, x1 = x2, x2 = tmp;
	if (y1 > y2)
		tmp = y1, y1 = y2, y2 = tmp;
	if (x3 > x4)
		tmp = x3, x3 = x4, x4 = tmp;
	if (y3 > y4)
		tmp = y3, y3 = y4, y4 = tmp;
	return max(x1, x3) <= min(x2, x4) && max(y1, y3) <= min(y2, y4);
}

int get_ve(int *xx, int *yy, int n) {
	int i, j, ve;

	ve = n;
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (intersect(xx[i << 1 | 0], yy[i << 1 | 0], xx[i << 1 | 1], yy[i << 1 | 1], xx[j << 1 | 0], yy[j << 1 | 0], xx[j << 1 | 1], yy[j << 1 | 1]))
				ve--;
	return ve;
}

int get_c(int *xx, int *yy, int n) {
	int i, j, c;

	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (intersect(xx[i << 1 | 0], yy[i << 1 | 0], xx[i << 1 | 1], yy[i << 1 | 1], xx[j << 1 | 0], yy[j << 1 | 0], xx[j << 1 | 1], yy[j << 1 | 1]))
				join(i, j);
	c = 0;
	for (i = 0; i < n; i++)
		if (ds[i] < 0)
			c++;
	return c;
}

int main() {
	static int xx[N * 2], yy[N * 2];
	int w, h, n, i;

	scanf("%d%d%d", &w, &h, &n);
	for (i = 0; i < n * 2; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	xx[n << 1 | 0] = 0, yy[n << 1 | 0] = 0, xx[n << 1 | 1] = w, yy[n << 1 | 1] = 0;
	xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
	xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
	xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
	n += 4;
	printf("%d\n", get_c(xx, yy, n) - get_ve(xx, yy, n));
	return 0;
}

Compilation message

2014_ho_t5.c: In function 'main':
2014_ho_t5.c:77:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   77 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |     ~~^~~
2014_ho_t5.c:77:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   77 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |                             ~~^~~
2014_ho_t5.c:77:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   77 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |                                                     ~~^~~
2014_ho_t5.c:77:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   77 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |                                                                             ~~^~~
2014_ho_t5.c:78:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   78 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |     ~~^~~
2014_ho_t5.c:78:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   78 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |                             ~~^~~
2014_ho_t5.c:78:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   78 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |                                                     ~~^~~
2014_ho_t5.c:78:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   78 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |                                                                             ~~^~~
2014_ho_t5.c:79:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |     ~~^~~
2014_ho_t5.c:79:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |                             ~~^~~
2014_ho_t5.c:79:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |                                                     ~~^~~
2014_ho_t5.c:79:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |                                                                             ~~^~~
2014_ho_t5.c:73:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d%d%d", &w, &h, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.c:75:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 284 KB Output is correct
7 Correct 2 ms 288 KB Output is correct
8 Correct 7 ms 208 KB Output is correct
9 Correct 4 ms 208 KB Output is correct
10 Correct 7 ms 208 KB Output is correct
11 Correct 9 ms 208 KB Output is correct
12 Correct 3 ms 208 KB Output is correct
13 Correct 8 ms 208 KB Output is correct
14 Correct 5 ms 296 KB Output is correct
15 Correct 7 ms 208 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 288 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 284 KB Output is correct
7 Correct 2 ms 288 KB Output is correct
8 Correct 7 ms 208 KB Output is correct
9 Correct 4 ms 208 KB Output is correct
10 Correct 7 ms 208 KB Output is correct
11 Correct 9 ms 208 KB Output is correct
12 Correct 3 ms 208 KB Output is correct
13 Correct 8 ms 208 KB Output is correct
14 Correct 5 ms 296 KB Output is correct
15 Correct 7 ms 208 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 288 KB Output is correct
18 Correct 1 ms 284 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 1 ms 208 KB Output is correct
21 Correct 6 ms 208 KB Output is correct
22 Correct 4 ms 208 KB Output is correct
23 Correct 6 ms 208 KB Output is correct
24 Correct 7 ms 208 KB Output is correct
25 Correct 7 ms 296 KB Output is correct
26 Correct 3 ms 324 KB Output is correct
27 Correct 8 ms 336 KB Output is correct
28 Correct 7 ms 292 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 3 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Runtime error 2 ms 592 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 280 KB Output is correct
2 Correct 9 ms 292 KB Output is correct
3 Runtime error 2 ms 520 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 284 KB Output is correct
7 Correct 2 ms 288 KB Output is correct
8 Correct 7 ms 208 KB Output is correct
9 Correct 4 ms 208 KB Output is correct
10 Correct 7 ms 208 KB Output is correct
11 Correct 9 ms 208 KB Output is correct
12 Correct 3 ms 208 KB Output is correct
13 Correct 8 ms 208 KB Output is correct
14 Correct 5 ms 296 KB Output is correct
15 Correct 7 ms 208 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 288 KB Output is correct
18 Correct 1 ms 284 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 1 ms 208 KB Output is correct
21 Correct 6 ms 208 KB Output is correct
22 Correct 4 ms 208 KB Output is correct
23 Correct 6 ms 208 KB Output is correct
24 Correct 7 ms 208 KB Output is correct
25 Correct 7 ms 296 KB Output is correct
26 Correct 3 ms 324 KB Output is correct
27 Correct 8 ms 336 KB Output is correct
28 Correct 7 ms 292 KB Output is correct
29 Correct 3 ms 208 KB Output is correct
30 Correct 3 ms 208 KB Output is correct
31 Correct 2 ms 208 KB Output is correct
32 Correct 5 ms 332 KB Output is correct
33 Runtime error 2 ms 592 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -