oj.uz

Submission #945424

# Submission time Handle Problem Language Result Execution time Memory
945424 2024-03-13T18:58:30 Z rainboy Multidrink (POI13_mul) C
100 / 100
 375 ms 55300 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6580 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10676 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 12636 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12720 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6584 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 19392 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 19284 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11508 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 43616 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 43636 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 46420 KB Output is correct
2 Correct 358 ms 46380 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 55028 KB Output is correct
2 Correct 280 ms 55300 KB Output is correct