oj.uz

Submission #781155

# Submission time Handle Problem Language Result Execution time Memory
781155 2023-07-12T19:47:58 Z rainboy Povjerenstvo (COI22_povjerenstvo) C
13 / 100
 383 ms 87524 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 186 ms 87524 KB Output is correct
2 Correct 148 ms 60424 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 86 ms 52584 KB Output is correct
5 Correct 103 ms 58280 KB Output is correct
6 Correct 134 ms 58328 KB Output is correct
7 Correct 108 ms 57196 KB Output is correct
8 Correct 158 ms 59188 KB Output is correct
9 Correct 239 ms 60408 KB Output is correct
10 Correct 272 ms 55628 KB Output is correct
11 Correct 294 ms 59780 KB Output is correct
12 Correct 347 ms 56304 KB Output is correct
13 Correct 226 ms 57700 KB Output is correct
14 Correct 237 ms 57952 KB Output is correct
15 Correct 189 ms 58176 KB Output is correct
16 Correct 187 ms 58148 KB Output is correct
17 Correct 41 ms 5924 KB Output is correct
18 Correct 70 ms 9824 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 87500 KB Output is correct
2 Correct 145 ms 59436 KB Output is correct
3 Correct 101 ms 54424 KB Output is correct
4 Correct 287 ms 58200 KB Output is correct
5 Correct 383 ms 60676 KB Output is correct
6 Incorrect 247 ms 57676 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 888 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Incorrect 2 ms 852 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 186 ms 87524 KB Output is correct
2 Correct 148 ms 60424 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 86 ms 52584 KB Output is correct
5 Correct 103 ms 58280 KB Output is correct
6 Correct 134 ms 58328 KB Output is correct
7 Correct 108 ms 57196 KB Output is correct
8 Correct 158 ms 59188 KB Output is correct
9 Correct 239 ms 60408 KB Output is correct
10 Correct 272 ms 55628 KB Output is correct
11 Correct 294 ms 59780 KB Output is correct
12 Correct 347 ms 56304 KB Output is correct
13 Correct 226 ms 57700 KB Output is correct
14 Correct 237 ms 57952 KB Output is correct
15 Correct 189 ms 58176 KB Output is correct
16 Correct 187 ms 58148 KB Output is correct
17 Correct 41 ms 5924 KB Output is correct
18 Correct 70 ms 9824 KB Output is correct
19 Correct 182 ms 87500 KB Output is correct
20 Correct 145 ms 59436 KB Output is correct
21 Correct 101 ms 54424 KB Output is correct
22 Correct 287 ms 58200 KB Output is correct
23 Correct 383 ms 60676 KB Output is correct
24 Incorrect 247 ms 57676 KB For each person outside the committee there should be someone in the committee who they dislike.
25 Halted 0 ms 0 KB -