結果

問題 No.177 制作進行の宮森あおいです！
ユーザー Shiro_S
提出日時 2020-09-28 21:26:52
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,265 bytes
コンパイル時間 1,415 ms
コンパイル使用メモリ 33,536 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-02 16:10:33
合計ジャッジ時間 2,568 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<time.h>
#include<stdio.h>
#include<unistd.h>
#include<string.h>
#include<stdlib.h>
#include<stdint.h>
#include<stdarg.h>
#include<tgmath.h>
#include<assert.h>
#include<iso646.h>
#include<stdbool.h>
inline int max(int a, int b){return a>b?a:b;}
inline int min(int a, int b){return b>a?a:b;}
#define MAX_V 111
typedef int32_t Cap;
const Cap Cap_MAX = INT32_MAX;
typedef struct mf_edge{
    int to;
    Cap cap;
    struct mf_edge *next, *rev;
} mf_edge;
typedef mf_edge* edge;
edge nil, G[MAX_V], iter[MAX_V];
int level[MAX_V];
void add_edge(int _from, int _to, Cap cap){
    edge go = (edge)malloc(sizeof(mf_edge));
    edge back = (edge)malloc(sizeof(mf_edge));
    *go = (mf_edge){_to, cap, G[_from], back};
    *back = (mf_edge){_from, 0, G[_to], go};
    G[_from] = go;
    G[_to] = back;
    return;
}
void maxflow_bfs(int s){
    for(int i=0; i<MAX_V; i++)level[i] = -1;
    int que[MAX_V], l = 0, r = 0;
    level[s] = 0;
    que[r++] = s;
    while(l != r){
        int v = que[l++]; l %= MAX_V;
        for(edge e = G[v]; e != nil; e = (*e).next){
            if((*e).cap > 0 && level[(*e).to] < 0){
                level[(*e).to] = level[v] + 1;
                que[r++] = (*e).to; r %= MAX_V;
            }
        }
    }
}
Cap maxflow_dfs(int v, int t, Cap f){
    if(v == t) return f;
    for(; iter[v] != nil; iter[v] = (*iter[v]).next){
        edge e = iter[v];
        if((*e).cap > 0 && level[v] < level[(*e).to]){
            Cap d = maxflow_dfs((*e).to, t, f>(*e).cap?(*e).cap:f);
            if(d > 0){
                (*e).cap -= d;
                (*(*e).rev).cap += d;
                return d;
            }
        }
    }
    return 0;
}
Cap maxflow(int s, int t){
    Cap flow = 0;
    for(;;){
        maxflow_bfs(s);
        if(level[t] < 0) return flow;
        for(int i=0; i<MAX_V; i++)iter[i] = G[i];
        Cap f;
        while((f = maxflow_dfs(s, t, Cap_MAX)) > 0){
            flow += f;
        }
    }
}
int main(){
    int W, N, M;
    int s = 101, t = 102;
    scanf("%d%d", &W, &N);
    for(int i=0; i<N; i++){
        int J;
        scanf("%d", &J);
        add_edge(s, i, J);
    }
    scanf("%d", &M);
    for(int i=0; i<M; i++){
        int C;
        scanf("%d", &C);
        add_edge(50 + i, t, C);
    }
    for(int k=0; k<M; k++){
        int Q;
        scanf("%d", &Q);
        bool f[] = {[0 ... 55] true};
        for(int i=0; i<Q; i++){
            int X;
            scanf("%d", &X);
            f[X-1] = false;
        }
        for(int i=0; i<N; i++){
            if(f[i])add_edge(i, 50 + k, W);
        }
    }
    int T = maxflow(s, t);
    puts(T < W ? "BANSAKUTSUKITA" : "SHIROBAKO");
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0