#668622 (C) No.1615 Double Down

提出ソース

結果

問題	No.1615 Double Down
ユーザー	ygussany
提出日時	2021-06-20 20:29:34
言語	C (gcc 12.3.0)
結果	AC
実行時間	1,386 ms / 10,000 ms
コード長	5,777 bytes
コンパイル時間	423 ms
コンパイル使用メモリ	35,456 KB
実行使用メモリ	21,584 KB
最終ジャッジ日時	2024-07-17 15:16:57
合計ジャッジ時間	18,738 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	106 ms 12,208 KB
testcase_01	AC	103 ms 14,216 KB
testcase_02	AC	150 ms 16,896 KB
testcase_03	AC	154 ms 16,700 KB
testcase_04	AC	126 ms 17,516 KB
testcase_05	AC	132 ms 17,436 KB
testcase_06	AC	162 ms 18,028 KB
testcase_07	AC	169 ms 17,160 KB
testcase_08	AC	168 ms 19,004 KB
testcase_09	AC	864 ms 18,868 KB
testcase_10	AC	888 ms 18,884 KB
testcase_11	AC	773 ms 16,932 KB
testcase_12	AC	260 ms 18,620 KB
testcase_13	AC	291 ms 18,612 KB
testcase_14	AC	266 ms 18,792 KB
testcase_15	AC	222 ms 19,480 KB
testcase_16	AC	221 ms 19,600 KB
testcase_17	AC	244 ms 21,584 KB
testcase_18	AC	1,333 ms 20,104 KB
testcase_19	AC	1,386 ms 18,628 KB
testcase_20	AC	1,196 ms 20,796 KB
testcase_21	AC	1,246 ms 18,636 KB
testcase_22	AC	1,223 ms 18,768 KB
testcase_23	AC	1,244 ms 17,832 KB
testcase_24	AC	1,025 ms 18,768 KB
testcase_25	AC	1,087 ms 18,880 KB
testcase_26	AC	1,003 ms 18,812 KB
testcase_27	AC	21 ms 9,580 KB
testcase_28	AC	20 ms 9,648 KB
testcase_29	AC	35 ms 9,900 KB
testcase_30	AC	35 ms 13,572 KB
testcase_31	AC	35 ms 11,324 KB
testcase_32	AC	34 ms 10,000 KB
testcase_33	AC	50 ms 10,336 KB
testcase_34	AC	48 ms 10,200 KB
testcase_35	AC	49 ms 10,336 KB
testcase_36	AC	4 ms 8,288 KB
testcase_37	AC	4 ms 8,340 KB
testcase_38	AC	5 ms 8,396 KB
testcase_39	AC	5 ms 8,884 KB
testcase_40	AC	4 ms 6,944 KB
testcase_41	AC	4 ms 8,892 KB
testcase_42	AC	5 ms 8,448 KB
testcase_43	AC	6 ms 8,780 KB
testcase_44	AC	5 ms 8,784 KB
testcase_45	AC	3 ms 8,784 KB
testcase_46	AC	2 ms 8,068 KB
testcase_47	AC	3 ms 6,944 KB
testcase_48	AC	3 ms 8,704 KB
testcase_49	AC	3 ms 8,848 KB
testcase_50	AC	3 ms 8,616 KB
testcase_51	AC	3 ms 8,724 KB
testcase_52	AC	3 ms 8,160 KB
testcase_53	AC	3 ms 8,260 KB
testcase_54	AC	3 ms 8,848 KB
testcase_55	AC	3 ms 6,944 KB
testcase_56	AC	2 ms 8,108 KB

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

ソースコード

raw source code

#include <stdio.h>
#include <stdlib.h>

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

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

const int sup = 1 << 30;

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 = (int*)malloc(sizeof(int) * (N + 1)), *dist = (int*)malloc(sizeof(int) * (N + 1)), *q = (int*)malloc(sizeof(int) * (N + 1)), head, tail;
	list **aux = (list**)malloc(sizeof(list*) * (N + 1)), *df = (list*)malloc(sizeof(list) * (M + 1)), *p;
	edge *f = (edge*)malloc(sizeof(edge) * (M + 1));
	for (i = 0; i < M; i++) f[i].flow = 0;
	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);
	
	free(par);
	free(dist);
	free(q);
	free(aux);
	free(df);
	free(f);
	return ans;
}

long long solve(int N, int M, int K, int L, int X[], int Y[], int Z[])
{
	int i, k, m = 0, F = 0, F_tmp, u, w, s = N + M + 1, t = N + M + 2, bit[31], flag[200003] = {}, tmp[200003], q[200003], head, tail;
	long long ans = 0;
	list *adj[200003] = {}, d[800001], *p, *pp;
    edge e[800001];
	for (i = 1, bit[0] = 1; i <= K; i++) bit[i] = bit[i-1] << 1;
	for (i = 1; i <= N; i++) {
		u = s;
		w = i;
		e[m].id = m;
		e[m].tail = u;
		e[m].head = w;
		e[m].flow = 0;
		e[m].cap = 1;
		e[m].cost = K;
		d[m].e = &(e[m]);
		d[m].next = adj[u];
		adj[u] = &(d[m++]);
		e[m].id = m;
		e[m].tail = w;
		e[m].head = u;
		e[m].flow = 0;
		e[m].cap = 0;
		e[m].cost = K;
		d[m].e = &(e[m]);
		d[m].next = adj[w];
		adj[w] = &(d[m++]);
	}
	for (i = 1; i <= M; i++) {
		u = i + N;
		w = t;
		e[m].id = m;
		e[m].tail = u;
		e[m].head = w;
		e[m].flow = 0;
		e[m].cap = 1;
		e[m].cost = K;
		d[m].e = &(e[m]);
		d[m].next = adj[u];
		adj[u] = &(d[m++]);
		e[m].id = m;
		e[m].tail = w;
		e[m].head = u;
		e[m].flow = 0;
		e[m].cap = 0;
		e[m].cost = K;
		d[m].e = &(e[m]);
		d[m].next = adj[w];
		adj[w] = &(d[m++]);
	}
	for (k = K; k >= 0; k--) {
		for (i = 1; i <= L; i++) {
			u = X[i];
			w = Y[i] + N;
			if (Z[i] != k || flag[u] != 0 || flag[w] != 0) continue;
			e[m].id = m;
			e[m].tail = u;
			e[m].head = w;
			e[m].flow = 0;
			e[m].cap = 1;
			e[m].cost = k;
			d[m].e = &(e[m]);
			d[m].next = adj[u];
			adj[u] = &(d[m++]);
			e[m].id = m;
			e[m].tail = w;
			e[m].head = u;
			e[m].flow = 0;
			e[m].cap = 0;
			e[m].cost = k;
			d[m].e = &(e[m]);
			d[m].next = adj[w];
			adj[w] = &(d[m++]);
		}
		F_tmp = Dinic(t, m, adj, e, s, t);
		ans += (long long)(F_tmp - F) * bit[k];
		F = F_tmp;
		
		for (u = 1; u <= t; u++) tmp[u] = 0;
		q[0] = s;
		tmp[s] = 1;
		for (head = 0, tail = 1; head < tail; head++) {
			u = q[head];
			for (pp = adj[u]; pp != NULL; pp = pp->next) {
				if (pp->e->flow == pp->e->cap || pp->e->head >= s) continue;
				w = pp->e->head;
				if (tmp[w] == 0) {
					tmp[w] = -tmp[u];
					q[tail++] = w;
				}
			}
		}
		q[0] = t;
		tmp[t] = 1;
		for (head = 0, tail = 1; head < tail; head++) {
			u = q[head];
			for (pp = adj[u]; pp != NULL; pp = pp->next) {
				if (e[pp->e->id ^ 1].flow == e[pp->e->id ^ 1].cap || pp->e->head >= s) continue;
				w = pp->e->head;
				if (tmp[w] == 0) {
					tmp[w] = -tmp[u];
					q[tail++] = w;
				}
			}
		}
		for (i = 0; i < m; i += 2) {
			u = e[i].tail;
			w = e[i].head;
			if (e[i].cap == 0 && e[i^1].cap == 0) continue;
			if (u == s) {
				if (tmp[w] == 0) {
					e[i].cap = 0;
					if (e[i].flow != 0) F--;
				} else e[i].cap = 1;
			} else if (w == t) {
				if (tmp[u] == 0) e[i].cap = 0;
				else e[i].cap = 1;
			} else {
				if (tmp[u] == 0 || tmp[w] == 0 || tmp[u] + tmp[w] == 2) e[i].cap = 0;
				else e[i].cap = 1;
			}
			e[i].flow = 0;
			e[i^1].cap = 0;
		}
		for (u = 1; u <= N + M; u++) if (flag[u] == 0 && tmp[u] >= 0) flag[u] = k;
	}
	return ans;
}

int main()
{
	int i, j, N, M, K, L, r, X[200001], Y[200001], Z[200001];
	scanf("%d %d %d %d", &N, &M, &K, &L);
	for (i = 1; i <= L; i++) scanf("%d %d %d", &(X[i]), &(Y[i]), &(Z[i]));
	printf("%lld\n", solve(N, M, K, L, X, Y, Z));
	fflush(stdout);
	return 0;
}

yukicoder

結果

テストケース

ソースコード