Submission #473042

#TimeUsernameProblemLanguageResultExecution timeMemory
473042rainboyPlaninarenje (COCI18_planinarenje)C11
160 / 160
3 ms716 KiB
/* http://blog.brucemerry.org.za/2018/01/coci-20172018-r5-analysis.html */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define N 5000 int *ev[N + 1], eo[N + 1], eo_[N + 1], n; void append(int u, int v) { int o = eo[u]++; if (o >= 2 && (o & o - 1) == 0) ev[u] = (int *) realloc(ev[u], o * 2 * sizeof *ev[u]); ev[u][o] = v; } int vv[N + 1], uu[N + 1], dd[N + 1]; int bfs() { static int qu[N]; int u, head, cnt; for (u = 0; u <= n; u++) dd[u] = n; head = cnt = 0; for (u = 1; u <= n; u++) if (!vv[u]) dd[u] = 0, qu[head + cnt++] = u; while (cnt) { int d, o; u = qu[cnt--, head++], d = dd[u] + 1; for (o = eo[u]; o--; ) { int v = ev[u][o], w = uu[v]; if (dd[w] == n) { dd[w] = d; if (w == 0) return 1; qu[head + cnt++] = w; } } } return 0; } int dfs(int u) { int d, o; if (u == 0) return 1; d = dd[u] + 1; for (o = eo_[u]; o--; ) { int v = ev[u][o], w = uu[v]; if (dd[w] == d && dfs(w)) { vv[u] = v, uu[v] = u; eo_[u] = o + 1; return 1; } } dd[u] = n; return 0; } void hopcroft_karp() { int u; while (bfs()) { memcpy(eo_, eo, (n + 1) * sizeof *eo); for (u = 1; u <= n; u++) if (vv[u] == 0) dfs(u); } } int main() { int m, u, v; scanf("%d%d", &n, &m); for (u = 1; u <= n; u++) ev[u] = (int *) malloc(2 * sizeof *ev[u]); while (m--) { scanf("%d%d", &u, &v); append(u, v); } hopcroft_karp(); for (u = 1; u <= n; u++) printf(dd[u] != n ? "Mirko\n" : "Slavko\n"); return 0; }

Compilation message (stderr)

planinarenje.c: In function 'append':
planinarenje.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   13 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
planinarenje.c: In function 'main':
planinarenje.c:81:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
planinarenje.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d%d", &u, &v);
      |   ^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...