結果

問題 No.177 制作進行の宮森あおいです！
ユーザー glretoglreto
提出日時 2020-11-13 19:21:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,757 bytes
コンパイル時間 2,147 ms
コンパイル使用メモリ 183,864 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-22 20:20:07
合計ジャッジ時間 2,829 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<bits//stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define req(i,n) for(int i = 1;i <=  n; i++)
#define rrep(i,n) for(ll i = n-1;i >= 0;i--)
#define ALL(obj) begin(obj), end(obj)
#define RALL(a) rbegin(a),rend(a)
typedef long long int ll;
typedef long double ld;
using pll = pair<ll,int>;
const int MAX = 510000;
const ll MOD = 1000000007;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1e18;
struct Dinic {
    struct edge {
        ll to,cap,rever;
        edge(ll to,ll cap, ll rever) :to(to), cap(cap), rever(rever) {}
    };
    vector< vector<edge> > graph;
    vector<int> level, iter;
    Dinic(ll V) :graph(V), level(V), iter(V) {}
    void add_edge(ll from, ll to,ll cap) {
        graph[from].emplace_back(to, cap, graph[to].size());
        graph[to].emplace_back(from, 0, graph[from].size() - 1);
    }
    void bfs(int s) {
        fill(ALL(level), -1);
        queue<ll> que;
        level[s] = 0;
        que.push(0);
        while (que.size()) {
            ll v = que.front(); que.pop();
            for (edge& e : graph[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    ll dfs(ll v, ll t,ll f) {
        if (v == t) return f;
        for (int& i = iter[v]; i < graph[v].size(); i++) {
            edge& e = graph[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                ll d = dfs(e.to, t, min(e.cap, f));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rever].cap += d;
                    return d;
                }
            }
        }return 0;
    }
    ll max_flow(int s, int t) {
       ll flow = 0;
       while (1) {
           bfs(s);
           if (level[t] < 0) return flow;
           fill(ALL(iter), 0);
           ll f; while ((f = dfs(s, t, 1e15)) > 0) flow += f;
       }
    }
};
int main(){
    int w,n,m,c;cin >> w>>n;vector<int> J(n),C(51);
    rep(i,n) cin >> J[i];
    cin >>m;Dinic dn(n+m+2);
    vector<vector<int>> G(n,vector<int>(m,1));
    rep(i,n) dn.add_edge(0,i+1,J[i]);
    rep(j,m) {
        cin >> C[j];dn.add_edge(j+n+1,n+m+1,C[j]);
    }
    rep(i,m){
        int q;cin >>q;
        rep(j,q){
            int x; cin >>x;x--;G[x][i]=0;
        }
    }rep(i,n){
        rep(j,m){
            if(G[i][j]) dn.add_edge(i+1,j+1+n,MOD);
        }
    }ll ans = dn.max_flow(0,n+m+1);
    if(ans >= w)cout << "SHIROBAKO" <<endl;
    else cout << "BANSAKUTSUKITA" <<endl;
}
0