結果

問題 No.177 制作進行の宮森あおいです！
ユーザー bal4ubal4u
提出日時 2019-07-21 19:17:02
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,422 bytes
コンパイル時間 1,335 ms
コンパイル使用メモリ 31,360 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-22 18:18:56
合計ジャッジ時間 2,098 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:8:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
    8 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:14:24: note: in expansion of macro 'gc'
   14 |         int n = 0, c = gc();
      |                        ^~

ソースコード

diff # 

// yukicoder: No.177 制作進行の宮森あおいです
// 2019.7.21 bal4u

#include <stdio.h>
#include <string.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}


/*******************************************/
/* Dinic's Max Flow Algorithm 
/*******************************************/
#define INF 0x01010101
#define VMAX 105
typedef struct { int to; int cap; int rev; } EDGE;
EDGE edge[VMAX][VMAX]; int hi[VMAX];
int V;				// 頂点数
int level[VMAX], iter[VMAX];
int queue[VMAX], qtop;

void add_edge(int from, int to, int cap) {
	int f, t;
	EDGE *e;

	f = hi[from]++, t = hi[to]++;
	e = &edge[from][f], e->to = to, e->cap = cap, e->rev = t;
//	e = &edge[to][t], e->to = from, e->cap = 0,   e->rev = f;
	e = &edge[to][t], e->to = from, e->cap = cap, e->rev = f;
}

void bfs(int s) {
	int i, v;
	EDGE *e;
	
	memset(level, -1, sizeof(int)*V);
	level[s] = 0;
	queue[0] = s, qtop = 1;
	while (qtop) {
		v = queue[--qtop];
		for (i = 0; i < hi[v]; i++) {
			e = &edge[v][i];
			if (e->cap > 0 && level[e->to] < 0) {
				level[e->to] = level[v] + 1;
				queue[qtop++] = e->to;
			}
		}
	}
}
 
int dfs(int v, int t, int f) {
	int *i, d;
	EDGE *e;
	
	if (v == t) return f;
	for (i = &iter[v]; *i < hi[v]; (*i)++) {
		e = &edge[v][*i];
		if (e->cap > 0 && level[v] < level[e->to]) {
			d = dfs(e->to, t, f <= e->cap? f: e->cap);
			if (d > 0) {
				e->cap -= d;
				edge[e->to][e->rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}
 
int maxFlow(int s, int t) {
	int f, flow = 0;
	while (1) {
		bfs(s);
		if (level[t] < 0) break;
		memset(iter, 0, sizeof(int)*V);
		while ((f = dfs(s, t, INF)) > 0) flow += f;
	}
	return flow;
}

/**********************************************/


int J[53];
char f[53];
int main()
{
	int i, j, W, N, M, S, T, Q;

	W = in();
	S = 0, T = 1;
	N = in(); for (i = 0; i < N; i++) add_edge(S, 2+i, J[i] = in());  // 各原画マンが描ける絵の数
	M = in(); for (i = 0; i < M; i++) add_edge(N+2+i, T, in()); // 各監督が仕上げる絵の数
	for (i = 0; i < M; i++) {
		memset(f, 0, sizeof(f));
		Q = in(); while (Q--) f[in()-1] = 1;
		for (j = 0; j < N; j++) if (!f[j]) add_edge(2+j, N+2+i, J[j]); // 相性のいい原画マンと監督
	}
	V = 2 + N + M;
	puts(maxFlow(S, T) >= W? "SHIROBAKO": "BANSAKUTSUKITA");
	return 0;
}
0