Submission #767605

#TimeUsernameProblemLanguageResultExecution timeMemory
767605rainboyMarriage questions (IZhO14_marriage)C11
100 / 100
284 ms1100 KiB
/* https://oj.uz/submission/100855 (Benq) */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define NU 30000 #define NV 2000 unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } int nu, nv; int *eu[NV], eo[NV], el[NV], er[NV]; int uu[NV], vv[NU]; char visited[NV]; void append(int v, int u) { int o = eo[v]++; if (o >= 2 && (o & o - 1) == 0) eu[v] = (int *) realloc(eu[v], o * 2 * sizeof *eu[v]); eu[v][o] = u; } void sort(int *ii, int l, int r) { while (l < r) { int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp; while (j < k) if (ii[j] == i_) j++; else if (ii[j] < i_) { tmp = ii[i], ii[i] = ii[j], ii[j] = tmp; i++, j++; } else { k--; tmp = ii[j], ii[j] = ii[k], ii[k] = tmp; } sort(ii, l, i); l = k; } } int dfs(int v) { int o; if (visited[v]) return 0; visited[v] = 1; for (o = el[v]; o < er[v]; o++) { int u = eu[v][o], w = vv[u]; if (w == -1 || dfs(w)) { uu[v] = u, vv[u] = v; return 1; } } return 0; } int check() { int v; for (v = 0; v < nv; v++) if (uu[v] == -1) { memset(visited, 0, nv * sizeof *visited); if (!dfs(v)) return 0; } return 1; } int main() { int m, h, l, r, u, v, ans; scanf("%d%d%d", &nu, &nv, &m); for (v = 0; v < nv; v++) eu[v] = (int *) malloc(2 * sizeof *eu[v]); for (h = 0; h < m; h++) { scanf("%d%d", &u, &v), u--, v--; append(v, u); } for (v = 0; v < nv; v++) sort(eu[v], 0, eo[v]); memset(uu, -1, nv * sizeof *uu), memset(vv, -1, nu * sizeof *vv); ans = 0; for (l = 0, r = -1; l < nu; l++) { while (r < nu && !check()) { r++; for (v = 0; v < nv; v++) if (er[v] < eo[v] && eu[v][er[v]] == r) er[v]++; } ans += nu - r; for (v = 0; v < nv; v++) { if (el[v] < eo[v] && eu[v][el[v]] == l) el[v]++; if (uu[v] == l) uu[v] = -1; } } printf("%d\n", ans); return 0; }

Compilation message (stderr)

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