oj.uz

Submission #781154

# Submission time Handle Problem Language Result Execution time Memory
781154 2023-07-12T19:45:18 Z rainboy Povjerenstvo (COI22_povjerenstvo) C
13 / 100
 389 ms 93780 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	500000
#define M	500000

int *ej[N], eo[N], *fi[N], fo[N], rr[N], qu[N], ii_[N], cnt;

void append(int **ej, int *eo, 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;
}

void dfs1(int i) {
	int o;

	if (rr[i])
		return;
	rr[i] = -1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs1(j);
	}
	qu[--cnt] = i;
}

void dfs2(int j, int r) {
	int o;

	if (rr[j] != -1)
		return;
	rr[j] = r;
	for (o = fo[j]; o--; ) {
		int i = fi[j][o];

		dfs2(i, r);
	}
}

int ds[N * 2];

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 cc[N]; char done[N];

void mark(int j, int c) {
	int o;

	if (done[j])
		return;
	cc[j] = c, done[j] = 1;
	if (c == 0) {
		for (o = fo[j]; o--; ) {
			int i = fi[j][o];

			if (!done[i] && --eo[i] == 0)
				ii_[cnt++] = i;
		}
	} else {
		for (o = fo[j]; o--; ) {
			int i = fi[j][o];

			mark(i, 0);
		}
	}
}

int main() {
	static int ii[M], jj[M];
	int n, m, h, h_, h1, i, j;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		fi[i] = (int *) malloc(2 * sizeof *fi[i]);
	}
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		ii[h] = i, jj[h] = j;
		append(ej, eo, i, j), append(fi, fo, j, i);
	}
	cnt = n;
	for (i = 0; i < n; i++)
		dfs1(i);
	for (h = 0; h < n; h++) {
		i = qu[h];
		dfs2(i, i);
	}
	memset(ds, -1, n * 2 * sizeof *ds);
	for (h = 0; h < m; h++) {
		i = ii[h], j = jj[h];
		if (rr[i] == rr[j])
			join(i << 1 | 0, j << 1 | 1), join(j << 1 | 0, i << 1 | 1);
	}
	for (i = 0; i < n; i++)
		cc[i] = find(i << 1 | 0) < find(i << 1 | 1) ? 0 : 1;
	cnt = 0;
	for (i = 0; i < n; i++)
		if (eo[i] == 0)
			ii_[cnt++] = i;
	for (h = n - 1; h >= 0; h = h_) {
		while (cnt)
			mark(ii_[--cnt], 1);
		h_ = h - 1;
		while (h_ >= 0 && rr[ii_[h_]] != rr[ii_[h]])
			h_--;
		for (h1 = h; h1 > h_; h1--)
			mark(ii_[h1], cc[ii_[h1]]);
	}
	cnt = 0;
	for (i = 0; i < n; i++)
		if (cc[i])
			ii_[cnt++] = i;
	printf("%d\n", cnt);
	while (cnt--)
		printf("%d ", ii_[cnt] + 1);
	printf("\n");
	return 0;
}

Compilation message

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

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 93712 KB Output is correct
2 Correct 135 ms 66560 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 87 ms 52576 KB Output is correct
5 Correct 96 ms 61352 KB Output is correct
6 Correct 131 ms 61988 KB Output is correct
7 Correct 103 ms 61200 KB Output is correct
8 Correct 143 ms 62932 KB Output is correct
9 Correct 252 ms 66464 KB Output is correct
10 Correct 258 ms 61148 KB Output is correct
11 Correct 287 ms 65708 KB Output is correct
12 Correct 332 ms 62032 KB Output is correct
13 Correct 241 ms 63696 KB Output is correct
14 Correct 240 ms 63984 KB Output is correct
15 Correct 185 ms 64284 KB Output is correct
16 Correct 182 ms 64200 KB Output is correct
17 Correct 37 ms 7872 KB Output is correct
18 Correct 64 ms 13360 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 93780 KB Output is correct
2 Correct 148 ms 63384 KB Output is correct
3 Correct 100 ms 58424 KB Output is correct
4 Correct 295 ms 64256 KB Output is correct
5 Correct 389 ms 67168 KB Output is correct
6 Incorrect 229 ms 63708 KB For each person outside the committee there should be someone in the committee who they dislike.
7 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 944 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Incorrect 2 ms 940 KB For each person outside the committee there should be someone in the committee who they dislike.
6 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 93712 KB Output is correct
2 Correct 135 ms 66560 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 87 ms 52576 KB Output is correct
5 Correct 96 ms 61352 KB Output is correct
6 Correct 131 ms 61988 KB Output is correct
7 Correct 103 ms 61200 KB Output is correct
8 Correct 143 ms 62932 KB Output is correct
9 Correct 252 ms 66464 KB Output is correct
10 Correct 258 ms 61148 KB Output is correct
11 Correct 287 ms 65708 KB Output is correct
12 Correct 332 ms 62032 KB Output is correct
13 Correct 241 ms 63696 KB Output is correct
14 Correct 240 ms 63984 KB Output is correct
15 Correct 185 ms 64284 KB Output is correct
16 Correct 182 ms 64200 KB Output is correct
17 Correct 37 ms 7872 KB Output is correct
18 Correct 64 ms 13360 KB Output is correct
19 Correct 156 ms 93780 KB Output is correct
20 Correct 148 ms 63384 KB Output is correct
21 Correct 100 ms 58424 KB Output is correct
22 Correct 295 ms 64256 KB Output is correct
23 Correct 389 ms 67168 KB Output is correct
24 Incorrect 229 ms 63708 KB For each person outside the committee there should be someone in the committee who they dislike.
25 Halted 0 ms 0 KB -