Submission #484307

#TimeUsernameProblemLanguageResultExecution timeMemory
484307rainboyMagenta (COCI21_magenta)C11
30 / 110
65 ms6344 KiB
#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; 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) { if (ddu[v] == n) for (o = eo[v]; o--; ) { h = eh[v][o], j = v ^ ij[h]; if (cc[h] <= 0 && ddu[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 (cc[h] <= 0) 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 (cc[h] <= 0 && ddv[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 (cc[h] >= 0) good2 = 1; } if (good1 && good2) { printf("Magenta\n"); return 0; } } printf("Marin\n"); } return 0; }

Compilation message (stderr)

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--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...