Submission #545889

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
545889	2022-04-05T15:54:40 Z	rainboy	Potemkin cycle (CEOI15_indcyc)	C	100 / 100	361 ms	2516 KB

indcyc

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

#define N	1000

int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int qu[N], cc[N], cnt; char adj[N];

void dfs(int i, int c) {
	int o;

	if (cc[i] == c)
		return;
	cc[i] = c;
	if (adj[i]) {
		qu[cnt++] = i;
		return;
	}
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(j, c);
	}
}

int bfs(int n, int s, int t, int c) {
	static int dd[N], pp[N];
	int i, head, cnt;

	for (i = 0; i < n; i++)
		dd[i] = n;
	head = cnt = 0;
	dd[s] = 0, pp[s] = -1, qu[head + cnt++] = s;
	while (cnt) {
		int d, o;

		i = qu[cnt--, head++], d = dd[i] + 1;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (cc[j] == c && (!adj[j] || j == t) && dd[j] > d) {
				dd[j] = d, pp[j] = i, qu[head + cnt++] = j;
				if (j == t) {
					cnt = 0;
					while (j != -1)
						qu[cnt++] = j, j = pp[j];
					return cnt;
				}
			}
		}
	}
	return -1;
}

int main() {
	static char aa[N][N];
	int n, m, h, h_, i, j;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	while (m--) {
		scanf("%d%d", &i, &j), i--, j--;
		aa[i][j] = aa[j][i] = 1;
		append(i, j), append(j, i);
	}
	for (i = 0; i < n; i++) {
		int o;

		memset(adj, 0, n * sizeof *adj);
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			adj[j] = 1;
		}
		memset(cc, -1, n * sizeof *cc);
		for (j = 0; j < n; j++)
			if (j != i && !adj[j] && cc[j] == -1) {
				cnt = 0;
				dfs(j, j);
				for (h = 0; h < cnt; h++)
					for (h_ = h + 1; h_ < cnt; h_++)
						if (!aa[qu[h]][qu[h_]]) {
							cnt = bfs(n, qu[h], qu[h_], j);
							while (cnt--)
								printf("%d ", qu[cnt] + 1);
							printf("%d\n", i + 1);
							return 0;
						}
			}
	}
	printf("no\n");
	return 0;
}

Compilation message

indcyc.c: In function 'append':
indcyc.c:12:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   12 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
indcyc.c: In function 'main':
indcyc.c:69:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
indcyc.c:73:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	680 KB	Output is correct
2	Correct	2 ms	596 KB	Output is correct
3	Correct	2 ms	664 KB	Output is correct
4	Correct	13 ms	724 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	596 KB	Output is correct
2	Correct	9 ms	648 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	2124 KB	Output is correct
2	Correct	6 ms	1680 KB	Output is correct
3	Correct	344 ms	2260 KB	Output is correct
4	Correct	148 ms	1768 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	1708 KB	Output is correct
2	Correct	133 ms	1716 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	2464 KB	Output is correct
2	Correct	17 ms	2444 KB	Output is correct
3	Correct	22 ms	2516 KB	Output is correct
4	Correct	361 ms	2476 KB	Output is correct