Submission #487026

#	Time	Username	Problem	Language	Result	Execution time	Memory
487026		rainboy	Ili (COI17_ili)	C11	100 / 100	2644 ms	1888 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;

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

	memset(state, -1, (n + m) * sizeof *state);
	for (j = n + m - 1; j >= 0; j--) {
		if (j >= n && cc[j - n] == '0')
			state[j] = 0;
		if (state[j] == 0)
			for (o = fo[j]; o--; ) {
				i = fi[j][o];
				state[i] = 0;
			}
	}
	for (i = 0; i < n + m; i++) {
		if (i < n && state[i] == -1)
			state[i] = 1;
		if (state[i] == 1)
			for (o = eo[i]; o--; ) {
				j = ej[i][o];
				state[j] = 1;
			}
	}
	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:52:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d%d%s", &n, &m, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
ili.c:61:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%s%s", aa, bb);
      |   ^~~~~~~~~~~~~~~~~~~~~

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