結果

問題 No.177 制作進行の宮森あおいです！
ユーザー なおなお
提出日時 2015-04-03 23:35:51
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,867 bytes
コンパイル時間 1,461 ms
コンパイル使用メモリ 161,216 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-17 04:02:17
合計ジャッジ時間 2,253 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define FOR(i, f, t)        for(int(i)=(f);(i)<(t);(++i))
#define RREP(i, n)          for(int(i)=(n)-1;(i)>=0;--(i))
#define FOREACH(it, c)      for(auto it=(c).begin();it!=(c).end();++it)
const int MOD = int(1e9+7);


// Dinic
class MaxFlow {
    int sa(int a, int b){ll c=(ll)a+b;return int(c<INF?c:INF);}
    int aug(const int u, const int t, const VI &P, VI &fin, int cur){
        if(u == t || cur == 0) return cur;
        if(fin[u]) return 0; fin[u] = true;
        int m = 0;
        FOREACH(it, E[u]){
            const int &v = *it;
            if(P[v] <= P[u]) continue;
            m = aug(v, t, P, fin, min(cur, C[u][v] - F[u][v]));
            if(m > 0){ F[u][v] += m; F[v][u] -= m; fin[u] = false; break; }
        }
        return m;
    }
public:
    static const int INF = 1<<29;
    VVI C, E, F;
    MaxFlow(int n) : C(n, VI(n)), E(n), F(n, VI(n)){;}
    void set(int u, int v, int c){
        if(C[u][v] == 0 && C[v][u] == 0) E[u].push_back(v); E[v].push_back(u);
        C[u][v] = c;
    }
    void add(int u, int v, int c){ set(u,v,sa(C[u][v],c));}
    int solve(const int s, const int t){
        int n = C.size(), f = 0; VI P(n), M(n); bool cont = true;
        while(cont){
            P = VI(n,-1); P[s] = 0; queue<int> q; q.push(s);
            for(int d = n; !q.empty() && P[q.front()] < d; ){
                int u = q.front(); q.pop();
                if(u == t) d = P[u];
                FOREACH(it, E[u]){
                    const int &v = *it;
                    if(P[v] >= 0 || C[u][v] - F[u][v] <= 0) continue;
                    P[v] = P[u]+1; q.push(v);
                }
            }
            VI fin(n); cont = false;
            while(1){
                int m = aug(s, t, P, fin, INF);
                if(m == 0) break;
                f += m; cont = true;
            }
        }
        return f;
    }
};

int W,N,J[55],M,C[55];

int res = 0;

int main(){
    do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0);
    cin >> W >> N;
    REP(i,N) cin >> J[i];
    cin >> M;
    REP(i,M) cin >> C[i];

    set<int> X[55];
    REP(i,M){
        int Q,x;
        cin >> Q;
        REP(j,Q){
            cin >> x;
            X[i].insert(x-1);
        }
    }

    // 0～49    : 原画(N)
    // 50～99   : 作監(M)
    // 100      : s
    // 101      : t
    MaxFlow mf(102);
    int s = 100, t = 101;

    REP(i,N) mf.set(s,i,J[i]);
    REP(i,M){
        const auto &x = X[i];
        REP(j,N){
            if(x.count(j)) continue;
            mf.set(j,50+i,mf.INF);
        }
        mf.set(50+i,t,C[i]);
    }

    cout << (mf.solve(s,t) >= W ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl;
    return 0;
}
0