結果

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

テストケース

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

ソースコード

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;
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(){
    ll w,n,m,c;cin >> w>>n;vector<ll> J(51),C(51);
    rep(i,n) cin >> J[i];
    cin >>m;Dinic dn(n+m+2);int st = n+m,g = n+m+1;
    vector<vector<int>> G(n,vector<int>(m,1));
    rep(i,n) dn.add_edge(st,i,J[i]);
    rep(j,m) {
        cin >> C[j];dn.add_edge(j+n,g,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,j+n,MAX);
        }
    }
    ll ans = dn.max_flow(st,g);
    cout << 0 <<endl;
    if(ans >= w)cout << "SHIROBAKO" <<endl;
    else cout << "BANSAKUTSUKITA" <<endl;
}
0