Submission #476125

#	Time	Username	Problem	Language	Result	Execution time	Memory
476125		rainboy	Priglavci (COCI18_priglavci)	C11	160 / 160	4 ms	588 KiB

priglvaci

#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 (stderr)

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]--;
      |    ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 160 / 160