oj.uz

Submission #544769

# Submission time Handle Problem Language Result Execution time Memory
544769 2022-04-02T16:36:23 Z rainboy Information (CEOI08_information) C
100 / 100
 614 ms 23004 KB 
/* http://i.stanford.edu/pub/cstr/reports/cs/tr/74/455/CS-TR-74-455.pdf */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	2000
#define M	1000000

int ii[M], jj[M]; char cc[M];
int *eh[N], eo[N]; char visited[N];
int hh1[N - 1], hh2[N - 1], cnt1, cnt2;

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

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

int ta[N], time;

void dfs1(int i) {
	int o;

	ta[i] = ++time;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = jj[h];

		if (!cc[h] && !ta[j])
			cc[h] = 1, hh1[cnt1++] = h, dfs1(j);
	}
}

void dfs2(int i) {
	int o;

	visited[i] = 1;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = jj[h];

		if (!cc[h] && !visited[j])
			cc[h] = 2, hh2[cnt2++] = h, dfs2(j);
	}
}

int main() {
	int n, m, h, i, j;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		ii[h] = i, jj[h] = j;
		append(i, h);
	}
	while (1) {
		int done, h_;

		memset(ta, 0, n * sizeof *ta), time = 0;
		cnt1 = 0;
		dfs1(0);
		for (i = 0; i < n; i++)
			if (!ta[i]) {
				printf("NONE\n");
				return 0;
			}
		memset(visited, 0, n * sizeof *visited);
		for (h = 0; h < cnt2; h++)
			cc[hh2[h]] = 0;
		cnt2 = 0;
		dfs2(0);
		done = 1;
		for (i = 0; i < n; i++)
			if (!visited[i]) {
				done = 0;
				break;
			}
		if (done)
			break;
		h_ = -1;
		for (h = 0; h < cnt1; h++) {
			int h1 = hh1[h];

			if (visited[ii[h1]] && !visited[jj[h1]])
				if (h_ == -1 || ta[ii[h_]] < ta[ii[h1]])
					h_ = h1;
			cc[h1] = 0;
		}
		cc[h_] = 2, hh2[cnt2++] = h_;
	}
	for (h = 0; h < cnt1; h++)
		printf("%d ", hh1[h] + 1);
	printf("\n");
	for (h = 0; h < cnt2; h++)
		printf("%d ", hh2[h] + 1);
	printf("\n");
	return 0;
}

Compilation message

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

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
4.0 / 4.0

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

Subtask #7
4.0 / 4.0

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

Subtask #8
4.0 / 4.0

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

Subtask #9
4.0 / 4.0

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

Subtask #10
4.0 / 4.0

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

Subtask #11
4.0 / 4.0

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

Subtask #12
4.0 / 4.0

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

Subtask #13
4.0 / 4.0

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

Subtask #14
4.0 / 4.0

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

Subtask #15
4.0 / 4.0

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

Subtask #16
4.0 / 4.0

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

Subtask #17
4.0 / 4.0

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

Subtask #18
4.0 / 4.0

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

Subtask #19
4.0 / 4.0

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

Subtask #20
4.0 / 4.0

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

Subtask #21
5.0 / 5.0

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

Subtask #22
5.0 / 5.0

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

Subtask #23
5.0 / 5.0

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

Subtask #24
5.0 / 5.0

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