結果

問題 No.177 制作進行の宮森あおいです！
ユーザー monnumonnu
提出日時 2020-04-04 03:12:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,435 bytes
コンパイル時間 1,969 ms
コンパイル使用メモリ 183,540 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-03 06:48:03
合計ジャッジ時間 2,826 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,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 3 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 3 ms
6,940 KB
testcase_13 AC 2 ms
6,940 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;
using ll=long long;
#define MOD 1000000007
#define INF 1000000000

typedef int FLOW;

struct Edge{
  int from,to;
  FLOW cap;
  Edge(int f,int t,FLOW c){
    from=f;
    to=t;
    cap=c;
  }
};

struct Graph{
  vector<vector<Edge>> list;
  Graph(int n){
    list.resize(n);
    for(int i=0;i<n;i++){
      //list.at(i).resize(n);
      for(int j=0;j<n;j++){
        list.at(i).push_back(Edge(i,j,0));
      }
    }
  }
  void push_back(int f,int t,int c){
    list.at(f).at(t)=Edge(f,t,c);
  }
  int size(){
    return list.size();
  }
  Edge& redge(Edge e){
    return list.at(e.to).at(e.from);
  }
};

vector<int> level;

void dibfs(Graph &G,int s){
  int N=G.size();
  level.resize(N);
  for(int i=0;i<N;i++){
    level.at(i)=-1;
  }
  level.at(s)=0;
  queue<int> q;
  q.push(s);
  while(!q.empty()){
    int v=q.front();
    q.pop();
    for(auto e:G.list.at(v)){
      if(e.cap>0&&level.at(e.to)==-1){
        level.at(e.to)=level.at(v)+1;
        q.push(e.to);
      }
    }
  }
}

FLOW didfs(Graph &G,int v,int t,FLOW f){
  if(v==t){
    return f;
  }
  for(auto &e:G.list.at(v)){
    if(e.cap>0&&level.at(v)<level.at(e.to)){
      FLOW d=didfs(G,e.to,t,min(f,e.cap));
      if(d>0){
        Edge &re=G.redge(e);
        e.cap-=d;
        re.cap+=d;
        return d;
      }
    }
  }
  return 0;
}

FLOW Dinic(Graph &G,int s,int t){
  FLOW res=0;
  while(true){
    dibfs(G,s);
    if(level.at(t)==-1){
      return res;
    }
    FLOW flow;
    while((flow=didfs(G,s,t,INF))>0){
      res+=flow;
    }
  }
}

int main(){
  int W,N;
  cin>>W>>N;
  vector<int> J(N);
  for(int i=0;i<N;i++){
    cin>>J.at(i);
  }
  int M;
  cin>>M;
  vector<int> C(M);
  for(int i=0;i<M;i++){
    cin>>C.at(i);
  }
  vector<int> Q(M);
  vector<vector<int>> X(M);
  for(int i=0;i<M;i++){
    cin>>Q.at(i);
    X.at(i).resize(Q.at(i));
    for(int j=0;j<Q.at(i);j++){
      cin>>X.at(i).at(j);
      X.at(i).at(j)--;
    }
  }
  int S=M+N;
  int T=M+N+1;

  Graph G(N+M+2);
  for(int i=0;i<N;i++){
    G.push_back(S,i,J.at(i));
  }
  for(int i=0;i<M;i++){
    G.push_back(i+N,T,C.at(i));
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      G.push_back(i,j+N,INF);
    }
  }
  for(int i=0;i<M;i++){
    for(int j=0;j<Q.at(i);j++){
      G.push_back(X.at(i).at(j),i+N,0);
    }
  }

  int w=Dinic(G,S,T);
  if(w<W){
    cout<<"BANSAKUTSUKITA"<<endl;
  }else{
    cout<<"SHIROBAKO"<<endl;
  }
}
0