#632728 (C) No.1479 Matrix Eraser

提出ソース

結果

問題	No.1479 Matrix Eraser
ユーザー	👑 ygussany
提出日時	2021-03-21 10:55:28
言語	C (gcc 12.3.0)
結果	AC
実行時間	1,456 ms / 3,000 ms
コード長	4,197 bytes
コンパイル時間	1,150 ms
コンパイル使用メモリ	32,400 KB
実行使用メモリ	37,236 KB
最終ジャッジ日時	2023-08-14 07:04:17
合計ジャッジ時間	20,417 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 14,280 KB
testcase_01	AC	5 ms 14,412 KB
testcase_02	AC	5 ms 14,152 KB
testcase_03	AC	5 ms 14,748 KB
testcase_04	AC	4 ms 14,148 KB
testcase_05	AC	5 ms 14,896 KB
testcase_06	AC	5 ms 15,060 KB
testcase_07	AC	24 ms 16,320 KB
testcase_08	AC	57 ms 15,732 KB
testcase_09	AC	237 ms 16,880 KB
testcase_10	AC	950 ms 17,168 KB
testcase_11	AC	322 ms 16,932 KB
testcase_12	AC	25 ms 16,488 KB
testcase_13	AC	45 ms 16,560 KB
testcase_14	AC	27 ms 14,940 KB
testcase_15	AC	6 ms 14,492 KB
testcase_16	AC	34 ms 16,468 KB
testcase_17	AC	1,450 ms 17,092 KB
testcase_18	AC	1,446 ms 17,376 KB
testcase_19	AC	1,441 ms 16,832 KB
testcase_20	AC	1,439 ms 18,028 KB
testcase_21	AC	1,448 ms 18,488 KB
testcase_22	AC	1,456 ms 16,828 KB
testcase_23	AC	1,448 ms 18,500 KB
testcase_24	AC	1,446 ms 17,276 KB
testcase_25	AC	1,435 ms 17,260 KB
testcase_26	AC	1,433 ms 17,404 KB
testcase_27	AC	132 ms 17,884 KB
testcase_28	AC	131 ms 17,028 KB
testcase_29	AC	132 ms 18,360 KB
testcase_30	AC	133 ms 17,664 KB
testcase_31	AC	134 ms 17,964 KB
testcase_32	AC	54 ms 37,016 KB
testcase_33	AC	58 ms 36,188 KB
testcase_34	AC	54 ms 36,112 KB
testcase_35	AC	54 ms 37,236 KB
testcase_36	AC	55 ms 35,788 KB
testcase_37	AC	23 ms 10,020 KB
testcase_38	AC	62 ms 17,296 KB
testcase_39	AC	34 ms 13,060 KB
testcase_40	AC	4 ms 9,972 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <stdio.h>

const int sup = 1 << 30;

typedef struct vList {
	struct vList *next;
	int i, j;
} vlist;

typedef struct {
	int id, head, tail, flow, cap;
} edge;

typedef struct List {
	struct List *next;
	edge *e;
} list;

void chmin(int* a, int b)
{
	if (*a > b) *a = b;
}

int DFS(list *aux[], edge f[], int par[], int u)
{
	int i, w, c, argmin;
	for (; aux[u] != NULL; aux[u] = aux[u]->next) {
		if (aux[u]->e->flow == aux[u]->e->cap) continue;
		w = aux[u]->e->head;
		if (par[w] == -3) {
			for (i = aux[u]->e->id, c = sup; par[w] != -2; i = par[w]) {
				chmin(&c, f[i].cap - f[i].flow);
				w = f[i].tail;
				if (f[i].cap - f[i].flow == c) argmin = w;
			}
			for (i = aux[u]->e->id, w = aux[u]->e->head; par[w] != -2; i = par[w]) {
				f[i].flow += c;
				w = f[i].tail;
			}
			if (argmin != u) {
				par[u] = -1;
				return argmin;
			}
		} else if (par[w] == -1) {
			par[w] = aux[u]->e->id;
			w = DFS(aux, f, par, w);
			if (w > 0 && w != u) {
				par[u] = -1;
				return w;
			}
		}
	}
	return 0;
}

int Dinic(int N, int M, list* adj[], edge e[], int s, int t)
{
	int i, u, w, ans = 0, add, par[1001], dist[1001], q[1001], head, tail;
	static list *aux[1001], df[500001], *p;
	static edge f[500001];
	do {
		for (u = 1; u <= N; u++) {
			dist[u] = -1;
			aux[u] = NULL;
		}
		dist[s] = 0;
		q[0] = s;
		for (head = 0, tail = 1; head < tail; head++) {
			u = q[head];
			for (p = adj[u]; p != NULL; p = p->next) {
				if (p->e->flow == p->e->cap) continue;
				w = p->e->head;
				if (dist[w] == -1) {
					dist[w] = dist[u] + 1;
					q[tail++] = w;
				}
				if (dist[w] == dist[u] + 1) {
					i = p->e->id;
					f[i].id = i;
					f[i].tail = u;
					f[i].head = w;
					f[i].flow = 0;
					f[i].cap = p->e->cap - p->e->flow;
					df[i].e = &(f[i]);
					df[i].next = aux[u];
					aux[u] = &(df[i]);
				}
			}
		}
		for (u = 1; u <= N; u++) par[u] = -1;
		par[s] = -2;
		par[t] = -3;
		DFS(aux, f, par, s);

		for (i = 0, add = 0; i < M; i++) {
			if (e[i].flow == e[i].cap || dist[e[i].head] != dist[e[i].tail] + 1 || f[i].flow == 0) continue;
			if (f[i].tail == s) add += f[i].flow;
			if (e[i^1].flow > 0) {
				e[i^1].flow -= f[i].flow;
				e[i].cap -= f[i].flow;
			} else {
				e[i].flow += f[i].flow;
				e[i^1].cap += f[i].flow;
			}
		}
		ans += add;
	} while (add != 0);
	return ans;
}

int main()
{
	int i, j, H, W, A[501][501];
	scanf("%d %d", &H, &W);
	for (i = 1; i <= H; i++) for (j = 1; j <= W; j++) scanf("%d", &(A[i][j]));

	int k, u, w, N = H + W, s = N + 1, t = N + 2, count[500001] = {}, ans = 0;
	vlist *appear[500001] = {}, d[250001], *p;
	list *adj[1001], f[500001];
	edge e[500001];
	for (i = 1, k = 0; i <= H; i++) {
		for (j = 1; j <= W; j++) {
			if (A[i][j] == 0) continue;
			else count[A[i][j]]++;
			d[k].i = i;
			d[k].j = j;
			d[k].next = appear[A[i][j]];
			appear[A[i][j]] = &(d[k++]);
		}
	}
	for (i = 1; i <= 500000; i++) {
		if (count[i] <= 1) {
			if (count[i] == 1) ans++;
			continue;
		}
		for (u = 1; u <= N + 2; u++) adj[u] = NULL;
		for (p = appear[i], k = 0; p != NULL; p = p->next) {
			u = p->i;
			w = p->j + H;
			
			e[k].id = k;
			e[k].tail = u;
			e[k].head = w;
			e[k].flow = 0;
			e[k].cap = 1;
			f[k].e = &(e[k]);
			f[k].next = adj[u];
			adj[u] = &(f[k++]);
			e[k].id = k;
			e[k].tail = w;
			e[k].head = u;
			e[k].flow = 0;
			e[k].cap = 0;
			f[k].e = &(e[k]);
			f[k].next = adj[w];
			adj[w] = &(f[k++]);
		}
		for (w = 1, u = s; w <= H; w++) {
			e[k].id = k;
			e[k].tail = u;
			e[k].head = w;
			e[k].flow = 0;
			e[k].cap = 1;
			f[k].e = &(e[k]);
			f[k].next = adj[u];
			adj[u] = &(f[k++]);
			e[k].id = k;
			e[k].tail = w;
			e[k].head = u;
			e[k].flow = 0;
			e[k].cap = 0;
			f[k].e = &(e[k]);
			f[k].next = adj[w];
			adj[w] = &(f[k++]);
		}
		for (u = H + 1, w = t; u <= N; u++) {
			e[k].id = k;
			e[k].tail = u;
			e[k].head = w;
			e[k].flow = 0;
			e[k].cap = 1;
			f[k].e = &(e[k]);
			f[k].next = adj[u];
			adj[u] = &(f[k++]);
			e[k].id = k;
			e[k].tail = w;
			e[k].head = u;
			e[k].flow = 0;
			e[k].cap = 0;
			f[k].e = &(e[k]);
			f[k].next = adj[w];
			adj[w] = &(f[k++]);
		}
		ans += Dinic(N + 2, k, adj, e, s, t);
	}
	printf("%d\n", ans);
	fflush(stdout);
	return 0;
}

yukicoder

結果

テストケース

ソースコード