Submission #719363

#	Time	Username	Problem	Language	Result	Execution time	Memory
719363		rainboy	Acrobat (balkan16_acrobat)	C11	100 / 100	290 ms	44204 KiB

main

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

#define N	300000
#define M	300000
#define K	(N * 5 / 2)

int ii[M], jj[M];
int *eh[N], eo[N];

void append(int i, int h) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

int cc[N], dd[N]; char visited[N], flip[M];

void dfs(int i) {
	int o;

	visited[i] = 1;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ii[h] ^ jj[h];

		if (!visited[j]) {
			dfs(j);
			if (cc[j])
				flip[h] = 1, cc[i] ^= 1, cc[j] ^= 1;
		}
	}
}

int main() {
	static int tt[K], uu[K], vv[K];
	int n, m, k, h, i, j;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		ii[h] = i, jj[h] = j;
		append(i, h), append(j, h);
		cc[i] ^= 1, dd[i] ^= 1, dd[j] ^= 1;
	}
	for (i = 0; i < n; i++)
		if (!visited[i])
			dfs(i);
	for (i = 0; i < n; i++)
		if (cc[i]) {
			printf("-1\n");
			return 0;
		}
	k = 0;
	for (h = 0; h < m; h++)
		if (flip[h])
			tt[k] = 1, uu[k] = ii[h], vv[k] = jj[h], k++;
	if (n > 1)
		for (i = 0; i < n; i++)
			tt[k] = 2, uu[k] = i, vv[k] = (i + 1) % n, k++;
	for (i = -1, j = 0; j < n; j++)
		if (dd[j] % 2 != 0) {
			if (i == -1)
				i = j;
			else
				tt[k] = 2, uu[k] = i, vv[k] = j, k++, i = -1;
		}
	printf("%d\n", k);
	while (k--)
		printf("%d %d %d\n", tt[k], uu[k] + 1, vv[k] + 1);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 30 / 30
• Subtask 2: 35 / 35
• Subtask 3: 35 / 35