結果

問題 No.177 制作進行の宮森あおいです！
ユーザー chocorusk
提出日時 2020-01-01 13:48:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,129 bytes
コンパイル時間 1,112 ms
コンパイル使用メモリ 117,548 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-22 02:08:32
合計ジャッジ時間 1,934 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

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

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll INF=1e18;
struct edge {int to; ll cap; int rev;} ;
vector<edge> G[200];
int level[200];
int iter[200];
void add_edge(int from, int to, ll cap){
    edge e;
    e.to=to, e.cap=cap, e.rev=G[to].size();
    G[from].push_back(e);
    e.to=from, e.cap=0, e.rev=G[from].size()-1;
    G[to].push_back(e);
}
void bfs(int s){
    memset(level, -1, sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v=que.front();
        que.pop();
        for(int i=0; i<G[v].size(); i++){
            edge e=G[v][i];
            if(e.cap>0 && level[e.to]<0){
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}
ll dfs(int v, int t, ll f){
    if(v==t) return f;
    for(int &i=iter[v]; i<G[v].size(); i++){
        edge &e=G[v][i];
        if(e.cap>0 && level[v]<level[e.to]){
            ll d=dfs(e.to, t, min(f, e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].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;
        memset(iter, 0, sizeof(iter));
        ll f;
        while((f=dfs(s, t, INF))>0){
            flow+=f;
        }
    }
}
int main()
{
    int w, n, m; cin>>w;
    cin>>n;
    int J[55];
    for(int i=0; i<n; i++){
        cin>>J[i];
    }
    cin>>m;
    int s=n+m, t=n+m+1;
    for(int i=0; i<n; i++) add_edge(s, i, J[i]);
    for(int i=0; i<m; i++){
        int c; cin>>c;
        add_edge(i+n, t, c);
    }
    for(int i=0; i<m; i++){
        bool b[55]={};
        int q; cin>>q;
        for(int j=0; j<q; j++){
            int x; cin>>x;
            b[x-1]=1;
        }
        for(int j=0; j<n; j++){
            if(!b[j]) add_edge(j, i+n, INF);
        }
    }
    if(max_flow(s, t)>=w) cout<<"SHIROBAKO"<<endl;
    else cout<<"BANSAKUTSUKITA"<<endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0