Submission #486980

#	Time	Username	Problem	Language	Result	Execution time	Memory
486980		rainboy	Ili (COI17_ili)	C11	49 / 100	4081 ms	1868 KiB

ili

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

#define N	10000
#define M	10000

int *ej[N + M], eo[N + M], *fi[N + M], fo[N + M];

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;
}

char state[N + M]; int n, m;

void dfs0(int j) {
	int o;

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

		dfs0(i);
	}
}

void dfs1(int i) {
	int o;

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

		dfs1(j);
	}
}

int check(char *cc) {
	int i, j;

	memset(state, -1, (n + m) * sizeof *state);
	for (j = 0; j < m; j++)
		if (cc[j] == '0')
			dfs0(n + j);
	for (i = 0; i < n; i++)
		if (state[i] == -1)
			dfs1(i);
	for (j = 0; j < m; j++)
		if (cc[j] == '1' && state[n + j] != 1)
			return 0;
	return 1;
}

int main() {
	static char cc[M + 1];
	int i, j;

	scanf("%d%d%s", &n, &m, cc);
	for (i = 0; i < n + m; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		fi[i] = (int *) malloc(2 * sizeof *fi[i]);
	}
	for (j = 0; j < m; j++) {
		static char aa[8], bb[8];
		int u, v;

		scanf("%s%s", aa, bb);
		u = atoi(aa + 1) + (aa[0] == 'x' ? 0 : n) - 1, v = atoi(bb + 1) + (bb[0] == 'x' ? 0 : n) - 1;
		append(ej, eo, u, n + j), append(fi, fo, n + j, u);
		append(ej, eo, v, n + j), append(fi, fo, n + j, v);
	}
	for (j = 0; j < m; j++)
		if (cc[j] == '?') {
			cc[j] = '0';
			if (!check(cc))
				cc[j] = '1';
			else {
				cc[j] = '1';
				cc[j] = !check(cc) ? '0' : '?';
			}
		}
	printf("%s\n", cc);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 0 / 51