제출 #447733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447733		rainboy	Flood (IOI07_flood)	C11	100 / 100	203 ms	30664 KiB

flood

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	100000

struct V {
	int ee[4], cnt, x, y, used;
} vv[N + N];

struct E {
	int a, b, ab, ba;
} ee[N * 2 + N];

int dsu[N * 4 + N];

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

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

struct L {
	struct L *next;
	int f;
};

struct F {
	struct L adj;
	int d;
} ff[N * 4 + N];

void link(int f1, int f2) {
	static struct L ll[2 * (N * 2 + N)], *x = ll;

	x->f = f2;
	x->next = ff[f1].adj.next; ff[f1].adj.next = x;
	x++;
	x->f = f1;
	x->next = ff[f2].adj.next; ff[f2].adj.next = x;
	x++;
}

int compare_v(const void *pi, const void *pj) {
	int i = *(int *) pi;
	int j = *(int *) pj;

	return vv[i].x != vv[j].x ? vv[i].x - vv[j].x : vv[i].y - vv[j].y;
}

int code(int x, int y) {
	return x == 0 ? (y < 0 ? 0 : 2) : (x < 0 ? 1 : 3);
}

int compare_e(const void *pi, const void *pj) {
	int i = *(int *) pi;
	int j = *(int *) pj;
	struct E *ei = &ee[i];
	struct E *ej = &ee[j];

	return code(vv[ei->b].x - vv[ei->a].x, vv[ei->b].y - vv[ei->a].y)
		- code(vv[ej->b].x - vv[ej->a].x, vv[ej->b].y - vv[ej->a].y);
}

void solve1(int a) {
	struct V *v = &vv[a];
	int h, m;

	if (v->used)
		return;
	v->used = 1;
	m = v->cnt;
	for (h = 0; h < m; h++) {
		struct E *e = &ee[v->ee[h]];

		if (e->a != a) {
			int tmp;

			tmp = e->a; e->a = e->b; e->b = tmp;
			tmp = e->ab; e->ab = e->ba; e->ba = tmp;
		}
	}
	qsort(v->ee, m, sizeof *v->ee, compare_e);
	for (h = 0; h < m; h++) {
		int ab = ee[v->ee[h]].ab, ba = ee[v->ee[(h + 1) % m]].ba;

		join(ab, ba);
	}
	for (h = 0; h < m; h++) {
		struct E *e = &ee[v->ee[h]];

		solve1(a ^ e->a ^ e->b);
	}
}

void solve2(int a) {
	struct V *v = &vv[a];
	int h, m;

	if (v->used == 2)
		return;
	v->used = 2;
	m = v->cnt;
	for (h = 0; h < m; h++) {
		struct E *e = &ee[v->ee[h]];
		int ab = find(e->ab), ba = find(e->ba);

		if (ab != ba && e->a != a)
			link(ab, ba);
		solve2(a ^ e->a ^ e->b);
	}
}

int dd[N * 4 + N];

void solve3(int a) {
	static int qq[N * 4 + N];
	int head, cnt, f;

	f = find(a);
	dd[f] = 0;
	head = cnt = 0;
	qq[head + cnt++] = f;
	while (cnt > 0) {
		struct L *x;

		f = qq[head++]; cnt--;
		for (x = ff[f].adj.next; x != NULL; x = x->next) {
			int f_ = x->f;

			if (dd[f_] > dd[f] + 1) {
				dd[f_] = dd[f] + 1;
				qq[head + cnt++] = f_;
			}
		}
	}
}

int main() {
	static int ii[N], ans[N * 2];
	int n, m, h, i, cnt;
	struct V *u, *v;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		v = &vv[i];
		scanf("%d%d", &v->x, &v->y);
	}
	scanf("%d", &m);
	for (h = 0; h < m; h++) {
		struct E *e = &ee[h];

		scanf("%d%d", &e->a, &e->b);
		e->a--, e->b--;
		u = &vv[e->a];
		v = &vv[e->b];
		u->ee[u->cnt++] = v->ee[v->cnt++] = h;
		e->ab = h * 2 + 0;
		e->ba = h * 2 + 1;
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	qsort(ii, n, sizeof *ii, compare_v);
	memset(dsu, -1, sizeof dsu);
	for (i = 0; i < m * 2 + n; i++)
		dd[i] = m * 2 + n;
	for (i = 0; i < n; i++) {
		int i_ = ii[i];
		struct V *u = &vv[i_];

		if (!u->used) {
			struct E *e = &ee[m + i];
			struct V *v = &vv[n + i];

			v->x = -1;
			v->y = u->y;
			v->cnt = 0;
			e->a = n + i;
			e->b = i_;
			e->ab = e->ba = m * 2 + i;
			u->ee[u->cnt++] = m + i;
			v->ee[v->cnt++] = m + i;
			solve1(n + i);
			solve2(n + i);
			solve3(m * 2 + i);
		}
	}
	cnt = 0;
	for (h = 0; h < m; h++) {
		int ab = find(ee[h].ab), ba = find(ee[h].ba);

		if (dd[ab] == dd[ba])
			ans[cnt++] = h + 1;
	}
	printf("%d\n", cnt);
	for (h = 0; h < cnt; h++)
		printf("%d\n", ans[h]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

flood.c: In function 'main':
flood.c:156:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
flood.c:159:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |   scanf("%d%d", &v->x, &v->y);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.c:161:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |  scanf("%d", &m);
      |  ^~~~~~~~~~~~~~~
flood.c:165:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   scanf("%d%d", &e->a, &e->b);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9