Submission #945424

#	Time	Username	Problem	Language	Result	Execution time	Memory
945424		rainboy	Multidrink (POI13_mul)	C11	100 / 100	375 ms	55300 KiB

mul

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

#define N	500000

int *ej[N], eo[N];

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

void detach(int i, int j) {
	int o;

	for (o = eo[i]; o--; )
		if (ej[i][o] == j) {
			eo[i]--;
			while (o < eo[i])
				ej[i][o] = ej[i][o + 1], o++;
			return;
		}
}

int pp[N];

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

	pp[i] = p;
	if (p != -1)
		detach(i, p);
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(i, j);
	}
}

int ii[N], k;

void trace(int i) {
	if (i == -1)
		return;
	trace(pp[i]);
	ii[k++] = i;
}

int trace_(int *qu_, int i) {
	static int qu[N];
	int cnt, cnt_, o, j_, h;

	cnt = 0;
	while (eo[i] > 0) {
		qu[cnt++] = i;
		j_ = -1;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (eo[j] > 0) {
				if (j_ == -1)
					j_ = j;
				else
					return -1;
			}
		}
		if (j_ == -1)
			break;
		i = j_;
	}
	cnt_ = 0;
	for (h = 0; h < cnt; h++) {
		i = qu[h];
		if (h % 2 == 0)
			qu_[cnt_++] = i;
		else
			for (o = eo[i]; o--; ) {
				int j = ej[i][o];

				if (h + 1 == cnt || j != qu[h + 1])
					qu_[cnt_++] = j;
			}
	}
	for (h = cnt - 1; h >= 0; h--) {
		i = qu[h];
		if (h % 2 != 0)
			qu_[cnt_++] = i;
		else
			for (o = eo[i]; o--; ) {
				int j = ej[i][o];

				if (h + 1 == cnt || j != qu[h + 1])
					qu_[cnt_++] = j;
			}
	}
	return cnt_;
}

int main() {
	static int qu[N], qu1[N], qu2[N];
	int n, cnt, cnt1, cnt2, g, h, i, j, o, last;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	dfs(-1, 0);
	trace(n - 1);
	for (h = 0; h + 1 < k; h++)
		detach(ii[h], ii[h + 1]);
	cnt = 0, last = 0;
	for (h = 0; h < k; h++) {
		i = ii[h];
		cnt1 = 0, cnt2 = 0;
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (eo[j] > 0) {
				if (cnt1 == 0) {
					if ((cnt1 = trace_(qu1, j)) == -1) {
						printf("BRAK\n");
						return 0;
					}
				} else if (cnt2 == 0) {
					if ((cnt2 = trace_(qu2, j)) == -1) {
						printf("BRAK\n");
						return 0;
					}
				} else {
					printf("BRAK\n");
					return 0;
				}
			}
		}
		if (!last) {
			qu[cnt++] = i;
			if (eo[i] == 0)
				last = 1;
			else {
				last = 0;
				if (cnt2 > 0) {
					printf("BRAK\n");
					return 0;
				}
				for (g = cnt1 - 1; g >= 0; g--)
					qu[cnt++] = qu1[g];
				for (o = eo[i]; o--; ) {
					j = ej[i][o];
					if (eo[j] == 0)
						qu[cnt++] = j;
				}
			}
		} else {
			for (o = eo[i]; o--; ) {
				j = ej[i][o];
				if (eo[j] == 0)
					qu[cnt++] = j;
			}
			for (g = 0; g < cnt1; g++)
				qu[cnt++] = qu1[g];
			qu[cnt++] = i;
			if (cnt2 == 0)
				last = 1;
			else {
				last = 0;
				for (g = cnt2 - 1; g >= 0; g--)
					qu[cnt++] = qu2[g];
			}
		}
	}
	if (!last) {
		printf("BRAK\n");
		return 0;
	}
	for (h = 0; h < cnt; h++)
		printf("%d\n", qu[h] + 1);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5