Submission #955835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
955835	2024-03-31T14:25:41 Z	rainboy	Graphic Madness (CERC12_K)	C	1 / 1	17 ms	3676 KB

K

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

#define N1	1000
#define N2	1000
#define L	1000
#define N	(N1 + L + N2 + L)
#define M	(N + L)

int *ej[N], eo[N], n, n1, n2, l;

void append(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;
}

int read_() {
	static char s[8];
	int i;

	scanf("%s", s);
	i = atoi(s + 2) - 1;
	if (s[0] == 'A' && s[1] == 'S')
		i += n1;
	else if (s[0] == 'B' && s[1] == 'P')
		i += n1 + l;
	else if (s[0] == 'B' && s[1] == 'S')
		i += n1 + l + n2;
	return i;
}

void write_(int i) {
	if (i < n1)
		printf("AP%d", i + 1);
	else if (i < n1 + l)
		printf("AS%d", i - n1 + 1);
	else if (i < n1 + l + n2)
		printf("BP%d", i - (n1 + l) + 1);
	else
		printf("BS%d", i - (n1 + l + n2) + 1);
}

int ii[M], jj[M], m;

int dfs(int p, int i) {
	int o, d;

	d = eo[i] == 1 ? 1 : 0;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && dfs(i, j))
			ii[m] = i, jj[m] = j, m++, d++;
	}
	d %= 2;
	return d;
}

int qu[N];

int check() {
	static int uu[N], vv[N];
	int cnt, h, i, j, k;

	if (m != n)
		return 0;
	memset(uu, -1, n * sizeof *uu);
	memset(vv, -1, n * sizeof *vv);
	for (h = 0; h < m; h++) {
		i = ii[h], j = jj[h];
		if (uu[i] == -1)
			uu[i] = j;
		else if (vv[i] == -1)
			vv[i] = j;
		else
			return 0;
		if (uu[j] == -1)
			uu[j] = i;
		else if (vv[j] == -1)
			vv[j] = i;
		else
			return 0;
	}
	i = vv[0], j = 0, cnt = 0;
	do {
		qu[cnt++] = j;
		k = i ^ uu[j] ^ vv[j], i = j, j = k;
	} while (j != 0);
	return cnt == n;
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		int h, i, j;

		scanf("%d%d%d", &l, &n1, &n2);
		n = n1 + l + n2 + l;
		for (i = 0; i < n; i++)
			ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
		for (h = 0; h < n - 2; h++) {
			i = read_(), j = read_();
			append(i, j), append(j, i);
		}
		m = 0;
		for (h = 0; h < l; h++) {
			i = read_(), j = read_();
			ii[m] = i, jj[m] = j, m++;
		}
		if (dfs(-1, 0) || dfs(-1, n1 + l) || !check())
			printf("NO\n");
		else {
			printf("YES");
			for (h = 0; h < n; h++)
				printf(" "), write_(qu[h]);
			printf("\n");
		}
	}
	return 0;
}

Compilation message

K.c: In function 'append':
K.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
K.c: In function 'read_':
K.c:25:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%s", s);
      |  ^~~~~~~~~~~~~~
K.c: In function 'main':
K.c:99:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
K.c:103:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf("%d%d%d", &l, &n1, &n2);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	3676 KB	Output is correct
2	Correct	17 ms	3664 KB	Output is correct