oj.uz

Submission #447733

# Submission time Handle Problem Language Result Execution time Memory
447733 2021-07-27T12:12:25 Z rainboy Flood (IOI07_flood) C
100 / 100
 203 ms 30664 KB 
#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;
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2252 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2252 KB Output is correct
2 Correct 1 ms 2212 KB Output is correct
3 Correct 1 ms 2252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2252 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 3 ms 2380 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 1 ms 2252 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2252 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2252 KB Output is correct
2 Correct 2 ms 2380 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 2 ms 2380 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6132 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 17144 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 20384 KB Output is correct
2 Correct 195 ms 28972 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 27876 KB Output is correct
2 Correct 203 ms 26956 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 30664 KB Output is correct
2 Correct 120 ms 21188 KB Output is correct