結果

問題 No.177 制作進行の宮森あおいです！
ユーザー 沙耶花
提出日時 2020-05-07 15:07:57
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 2,456 bytes
コンパイル時間 3,972 ms
コンパイル使用メモリ 219,120 KB
最終ジャッジ日時 2025-01-10 07:27:50
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000000000
template <typename T>
struct Dinic{
    struct edge{
        int to;
        T weight;
        int ind;
    };
    vector<vector<edge>> E;
    T inf;
    
    Dinic(vector<vector<pair<int,T>>> &e,T iv = 1000000001){
        inf = iv;
        E.resize(e.size(),vector<edge>());
        for(int i=0;i<e.size();i++){
            for(int j=0;j<e[i].size();j++){
                edge t = {e[i][j].first,e[i][j].second,0};
                E[i].push_back(t);
            }
        }
        for(int i=0;i<e.size();i++){
            for(int j=0;j<e[i].size();j++){
                E[i][j].ind = E[E[i][j].to].size();
                edge t = {i,0,j};
                E[E[i][j].to].push_back(t);
            }
        }
    }
    
    T maximum_flow(int s,int t){
        
        T ret = 0;
        
        while(true){
            vector<int> dis(E.size(),-1);
            queue<int> Q;
            Q.push(s);
            dis[s] = 0;
            while(Q.size()!=0){
                int u = Q.front();
                Q.pop();
                for(int i=0;i<E[u].size();i++){
                    if(E[u][i].weight<=0)continue;
                    int v = E[u][i].to;
                    if(dis[v]!=-1)continue;
                    dis[v] = dis[u]+1;
                    Q.push(v);
                }
            }
            if(dis[t]==-1)break;
            
            vector<int> it(E.size(),0);
            
            while(true){
                T F = dfs(s,t,inf,it,dis);
                if(F==0)break;
                ret+=F;
            }
        }
        return ret;
    }
    
    T dfs(int now,int t,T f,vector<int> &it,vector<int> &dis){
        if(now==t)return f;
        
        for(int &i=it[now];i<E[now].size();i++){
            int to = E[now][i].to;
            T weight = E[now][i].weight;
            if(weight<=0||dis[now]+1!=dis[to]){
                continue;
            }
            T F = dfs(to,t,min(f,weight),it,dis);
            if(F!=0){
                E[now][i].weight-=F;
                E[E[now][i].to][E[now][i].ind].weight+=F;
                return F;
            }
        }
        return 0;
    }
    
};
int main(){
    int W,N;
    cin>>W>>N;
    
    vector<int> J(N);
    for(int i=0;i<N;i++)cin>>J[i];
    
    int M;
    cin>>M;
    
    vector<int> C(M);
    for(int i=0;i<M;i++)cin>>C[i];
    
    vector<vector<pair<int,long long>>> E(N+M+2,vector<pair<int,long long>>());
    
    vector<vector<bool>> B(N,vector<bool>(M,true));
    
    for(int i=0;i<M;i++){
        int Q;
        cin>>Q;
        for(int j=0;j<Q;j++){
            int X;
            cin>>X;
            X--;
            B[X][i] = false;
        }
    }
    
    for(int i=0;i<N;i++){
        E[N+M].emplace_back(i,J[i]);
        for(int j=0;j<M;j++){
            if(B[i][j]){
                E[i].emplace_back(N+j,Inf);
            }
        }
    }
    for(int i=0;i<M;i++){
        E[N+i].emplace_back(N+M+1,C[i]);
    }
    
    Dinic<long long> D(E,Inf);
    
    long long K = D.maximum_flow(N+M,N+M+1);
    //cout<<K<<endl;
    if(K>=W)cout<<"SHIROBAKO"<<endl;
    else cout<<"BANSAKUTSUKITA"<<endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0