結果

問題 No.177 制作進行の宮森あおいです！
ユーザー suzuken_wsuzuken_w
提出日時 2020-09-17 20:56:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 14 ms / 2,000 ms
コード長 2,903 bytes
コンパイル時間 2,986 ms
コンパイル使用メモリ 221,708 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-22 06:48:32
合計ジャッジ時間 3,558 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
const vector<int> dy={-1,0,1,0},dx={0,-1,0,1};
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T>void debag(const vector<T> &a){cerr<<"debag :";for(auto v:a)cerr<<v<<" ";cerr<<"\n";}
template<class T>void print(const vector<T> &a){for(auto v:a)cout<<v<<" ";cout<<"\n";}
const int MAX_V = 3000;
struct Flow{
    const ll INF=ll(1e9);
//辺の構造体　
struct edge{
    //行き先、容量、逆辺の場所
    ll to,cap,rev;
    edge(ll to,ll cap,ll rev):to(to),cap(cap),rev(rev){}
};
//グラフの隣接リスト
V<edge> G[MAX_V];//vectorの"配列"
//DFSで調べた頂点を記録
bool used[MAX_V]={};
//辺の情報を代入する関数
void add_edge(ll from,ll to,ll cap){
    G[from].emplace_back(to,cap,ll(G[to].size()));
    G[to].emplace_back(from,0,ll(G[from].size()-1));
}
//増加パスをDFSで探す
ll dfs(ll v,ll t,ll f){
    if(v==t)return f;
    used[v]=true;
    for(int i=0;i<G[v].size();i++){
        edge &e=G[v][i]; //辺の容量を更新するためのアドレス
        if(!used[e.to]&&e.cap>0){
            ll d=dfs(e.to,t,min<ll>(f,e.cap));
            if(d>0){
                e.cap-=d;//使った分減らす
                G[e.to][e.rev].cap+=d;//使った分逆辺の容量を増やす
                return d;
            }
        }
    }
    return 0;
}
//sからtへの最大流を求める
ll fmax(ll s,ll t){
   ll flow=0;
   while(1){
       for(int i=0;i<MAX_V;i++)used[i]=false;
       ll f=dfs(s,t,INF);
       if(f==0)return flow;
       flow+=f;
   }
}
};
int main(){
    int w;
    cin>>w;
    int n;
    cin>>n;
    V<int> j(n);
    for(int i=0;i<n;i++)cin>>j[i];
    int m;
    cin>>m;
    V<int> c(m);
    for(int i=0;i<m;i++)cin>>c[i];
    Flow flow;
    int S=0,T=n+m+2;
    for(int i=0;i<n;i++){
        flow.add_edge(S,i+1,j[i]);
    }
    for(int i=0;i<m;i++){
        flow.add_edge(i+n+1,T,c[i]);
    }
    int INF=(1e5);
    for(int i=0;i<m;i++){
        V<bool> ok(n,true);
        int q; cin>>q;
        for(int k=0;k<q;k++){
            int a;cin>>a;
            ok[a-1]=false;
        }
        for(int k=0;k<n;k++){
            if(ok[k]){
                flow.add_edge(k+1,i+n+1,INF);
            }
        }
    }
    if(w<=flow.fmax(S,T))cout<<"SHIROBAKO"<<"\n";
    else cout<<"BANSAKUTSUKITA"<<"\n";
}
0