結果

問題 No.177 制作進行の宮森あおいです！
ユーザー bal4u
提出日時 2019-07-21 19:17:02
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0