#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
#define M 100
#define K 100
#define N_ (1 + N + K + 1)
#define M_ (N + N * K + K)
#define INF 0x3f3f3f3f
int ii[M_], jj[M_], cc[M_ * 2], ww[M_], m_;
int *eh[N_], eo[N_], 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 add(int i, int j, int c, int w) {
int h = m_++;
ii[h] = i, jj[h] = j, cc[h << 1 | 0] = c, ww[h] = w;
append(i, h << 1 | 0), append(j, h << 1 | 1);
}
int dd[N_];
int bfs(int s, int t, int w) {
static int qu[N_];
int i, head, cnt;
for (i = 0; i < n_; i++)
dd[i] = n_;
head = cnt = 0;
dd[s] = 0, qu[head + cnt++] = s;
while (cnt) {
int d, o;
i = qu[cnt--, head++], d = dd[i] + 1;
for (o = eo[i]; o--; ) {
int h_ = eh[i][o], h = h_ >> 1;
if (cc[h_] && ww[h] <= w) {
int j = i ^ ii[h] ^ jj[h];
if (dd[j] > d) {
dd[j] = d;
if (j == t)
return 1;
qu[head + cnt++] = j;
}
}
}
}
return 0;
}
int eo_[N_];
int dfs(int i, int t, int w) {
int d, o;
if (i == t)
return 1;
d = dd[i] + 1;
for (o = eo_[i]; o--; ) {
int h_ = eh[i][o], h = h_ >> 1;
if (cc[h_] && ww[h] <= w) {
int j = i ^ ii[h] ^ jj[h];
if (dd[j] == d && dfs(j, t, w)) {
cc[h_]--, cc[h_ ^ 1]++;
eo_[i] = o + 1;
return 1;
}
}
}
dd[i] = n_;
eo_[i] = 0;
return 0;
}
int dinic(int s, int t, int w) {
int h, cnt;
for (h = 0; h < m_; h++)
cc[h << 1 | 0] += cc[h << 1 | 1], cc[h << 1 | 1] = 0;
cnt = 0;
while (bfs(s, t, w)) {
memcpy(eo_, eo, n_ * sizeof *eo);
while (dfs(s, t, w))
cnt++;
}
return cnt;
}
int main() {
static int xx[N + M], yy[N + M], jj_[N][K], jj1[N];
int n, m, c, k, g, h, h_, i, s, t, lower, upper;
scanf("%d%d%d%d", &n, &m, &c, &k);
for (i = 0; i < n + m; i++)
scanf("%d%d", &xx[i], &yy[i]);
n_ = 1 + n + k + 1, s = 0, t = n_ - 1;
for (i = 0; i < n_; i++)
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
for (i = 0; i < n; i++)
add(s, 1 + i, 1, 0);
for (h = 0; h < k; h++)
add(1 + n + h, t, c, 0);
for (h = 0; h < k; h++) {
static int jj[M];
int l;
scanf("%d", &l);
for (g = 0; g < l; g++)
scanf("%d", &jj[g]), jj[g]--;
for (i = 0; i < n; i++) {
int w_ = INF, j_ = -1;
for (g = 0; g < l; g++) {
int w = (xx[n + jj[g]] - xx[i]) * (xx[n + jj[g]] - xx[i]) + (yy[n + jj[g]] - yy[i]) * (yy[n + jj[g]] - yy[i]);
if (w_ > w)
w_ = w, j_ = jj[g];
}
add(1 + i, 1 + n + h, 1, w_);
jj_[i][h] = j_;
}
}
lower = -1, upper = INF;
while (upper - lower > 1) {
int w = (lower + upper) / 2;
if (dinic(s, t, w) == n)
upper = w;
else
lower = w;
}
if (upper == INF) {
printf("-1\n");
return 0;
}
dinic(s, t, upper);
for (h_ = 0; h_ < m_; h_++) {
i = ii[h_] - 1, h = jj[h_] - 1 - n;
if (i >= 0 && i < n && h >= 0 && h < k && cc[h_ << 1 | 1])
jj1[i] = jj_[i][h];
}
printf("%d\n", upper);
for (i = 0; i < n; i++)
printf("%d\n", jj1[i] + 1);
return 0;
}
Compilation message
priglvaci.c: In function 'append':
priglvaci.c:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
18 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
priglvaci.c: In function 'main':
priglvaci.c:106:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d%d%d%d", &n, &m, &c, &k);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.c:108:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.c:120:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | scanf("%d", &l);
| ^~~~~~~~~~~~~~~
priglvaci.c:122:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | scanf("%d", &jj[g]), jj[g]--;
| ^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
460 KB |
Output is correct |
| 4 |
Correct |
4 ms |
588 KB |
Output is correct |
| 5 |
Correct |
3 ms |
460 KB |
Output is correct |
| 6 |
Correct |
2 ms |
588 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
2 ms |
588 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
