#include "friend.h" #include <stdio.h> #include <stdlib.h> #include <string.h> #define N 1000 #define SMALL 10 int max(int a, int b) { return a > b ? a : b; } int *ev[N], eo[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[1 + N], uu[1 + N], dd[1 + N], eo_[1 + N], n_; int bfs() { static int qu[1 + 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_; eo_[u] = 0; return 0; } int hopcroft_karp() { int cnt; cnt = 0; while (bfs()) { int u; memcpy(eo_, eo, (n_ + 1) * sizeof *eo); for (u = 1; u <= n_; u++) if (!vv[u] && dfs(u)) cnt++; } return cnt; } int findSample(int n, int *aa, int *pp, int *tt) { static int bb[SMALL], cc[N], dp[N], dq[N]; static int adj[N][N]; int i, j, b, ans; ans = 0; if (n <= SMALL) { for (i = 1; i < n; i++) { if (tt[i] == 0) bb[i] = 1 << pp[i]; else if (tt[i] == 1) bb[i] = bb[pp[i]]; else bb[i] = bb[pp[i]] | 1 << pp[i]; for (j = 0; j < n; j++) if ((bb[i] & 1 << j) != 0) bb[j] |= 1 << i; } for (b = 0; b < 1 << n; b++) { int sum; sum = 0; for (i = 0; i < n; i++) if ((b & 1 << i) != 0) { if ((bb[i] & b) != 0) { sum = 0; break; } sum += aa[i]; } ans = max(ans, sum); } } else if (tt[1] == 2) { for (i = 0; i < n; i++) ans = max(ans, aa[i]); } else { for (i = 1; i < n; i++) if (tt[i] == 0) adj[i][pp[i]] = adj[pp[i]][i] = 1, cc[i] = cc[pp[i]] ^ 1; else if (tt[i] == 1) { for (j = 0; j < n; j++) if (adj[pp[i]][j]) adj[i][j] = adj[j][i] = 1; cc[i] = cc[pp[i]]; } for (i = 1; i <= n; i++) ev[i] = (int *) malloc(2 * sizeof *ev[i]); for (i = 0; i < n; i++) if (cc[i] == 0) for (j = 0; j < n; j++) if (cc[j] == 1 && adj[i][j]) append(1 + i, 1 + j); n_ = n; ans = n - hopcroft_karp(); } return ans; }

friend.c: In function 'append':
friend.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
friend.c: In function 'findSample':
friend.c:87:38: warning: unused variable 'dq' [-Wunused-variable]
   87 |  static int bb[SMALL], cc[N], dp[N], dq[N];
      |                                      ^~
friend.c:87:31: warning: unused variable 'dp' [-Wunused-variable]
   87 |  static int bb[SMALL], cc[N], dp[N], dq[N];
      |                               ^~
At top level:
friend.c:87:31: warning: 'dp' defined but not used [-Wunused-variable]
friend.c:87:38: warning: 'dq' defined but not used [-Wunused-variable]
   87 |  static int bb[SMALL], cc[N], dp[N], dq[N];
      |                                      ^~