oj.uz

Submission #484332

# Submission time Handle Problem Language Result Execution time Memory
484332 2021-11-02T23:37:38 Z rainboy Magenta (COCI21_magenta) C
30 / 110
 51 ms 6384 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	100000

int ij[N], cc[N];
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;
}

void dfs(int *dd, int p, int i, int d, int c) {
	int o;

	dd[i] = d;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];

		if (j != p && cc[h] * c >= 0)
			dfs(dd, i, j, d + 1, c);
	}
}

int main() {
	static int ddu[N], ddv[N];
	int n, u, v, h, i, j, d, o, marin;

	scanf("%d%d%d", &n, &u, &v), u--, v--;
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < n - 1; h++) {
		static char s[8];

		scanf("%d%d%s", &i, &j, s), i--, j--;
		ij[h] = i ^ j, cc[h] = s[0] == 'm' ? 0 : (s[0] == 'p' ? 1 : -1);
		append(i, h), append(j, h);
	}
	dfs(ddu, -1, u, 0, 0), d = ddu[v];
	for (i = 0; i < n; i++)
		ddu[i] = n;
	dfs(ddu, -1, u, 0, 1);
	for (i = 0; i < n; i++)
		ddv[i] = n;
	dfs(ddv, -1, v, 0, -1);
	if (d % 2 == 0) {
		marin = 1;
		for (o = eo[u]; o--; ) {
			h = eh[u][o], j = u ^ ij[h];
			if (cc[h] >= 0) {
				marin = 0;
				break;
			}
		}
		if (marin) {
			printf("Marin\n");
			return 0;
		}
		if (ddu[v] == n)
			for (o = eo[v]; o--; ) {
				h = eh[v][o], j = v ^ ij[h];
				if (ddu[j] == n && ddv[j] < n) {
					printf("Magenta\n");
					return 0;
				}
			}
		for (i = 0; i < n; i++)
			if (ddu[i] == n && ddv[i] < n) {
				int good1 = 0, good2 = 0;

				for (o = eo[i]; o--; ) {
					h = eh[i][o], j = i ^ ij[h];
					if (ddu[j] < n)
						good1 = ddv[j] < ddu[j];
					else if (ddv[j] < n)
						good2 = 1;
				}
				if (good1 && good2) {
					printf("Magenta\n");
					return 0;
				}
			}
		printf("Paula\n");
	} else {
		if (ddv[u] == n)
			for (o = eo[u]; o--; ) {
				h = eh[u][o], j = u ^ ij[h];
				if (ddv[j] == n && ddu[j] < n) {
					printf("Magenta\n");
					return 0;
				}
			}
		for (i = 0; i < n; i++)
			if (ddv[i] == n && ddu[i] < n) {
				int good1 = 0, good2 = 0;

				for (o = eo[i]; o--; ) {
					h = eh[i][o], j = i ^ ij[h];
					if (ddv[j] < n)
						good1 = ddu[j] <= ddv[j];
					else if (ddu[j] < n)
						good2 = 1;
				}
				if (good1 && good2) {
					printf("Magenta\n");
					return 0;
				}
			}
		printf("Marin\n");
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6360 KB Output is correct
2 Correct 45 ms 6384 KB Output is correct
3 Correct 45 ms 6324 KB Output is correct
4 Correct 46 ms 6320 KB Output is correct
5 Correct 45 ms 6340 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -