結果

問題 No.177 制作進行の宮森あおいです！
コンテスト
ユーザー is_eri23
提出日時 2014-11-23 15:38:13
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,975 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,121 ms
コンパイル使用メモリ 173,848 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-02 20:18:01
合計ジャッジ時間 2,679 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/*
  tester : atetubou's code
 */
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define F first
#define S second
#define SZ(a) (int)((a).size())
#define sz(a) SZ(a)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ALL(a) (a).begin(),(a).end()
using namespace std;

typedef long long ll;
typedef pair<ll,ll> PI;
typedef unsigned long long ull;

#define PR(...) do{cerr << "line : " << __LINE__ << endl; pr(#__VA_ARGS__, __VA_ARGS__);}while(0);
template<class T>
void pr(const string& name, T t){
  cerr << name << ": " << t << endl;
}

template<typename T, typename ... Types>
void pr(const string& names, T t, Types ... rest) {
  auto comma_pos = names.find(',');
  cerr << names.substr(0, comma_pos) << ": " << t << ", ";
  
  auto next_name_pos = names.find_first_not_of(" \t\n", comma_pos + 1);
  pr(string(names, next_name_pos), rest ...);
}

template<class T,class U> ostream& operator<< (ostream& o, const pair<T,U>& v){return o << "(" << v.F << ", " << v.S << ")";}
template<class T> ostream& operator<< (ostream& o, const vector<T>& v){o << "{";rep(i,SZ(v)) o << (i?", ":"") << v[i];return o << "}";}


#define endl '\n'

struct FlowGraphD{
  /*
    verified
    http://poj.org/problem?id=3469
    http://poj.org/problem?id=2987
  */
  
  typedef ll Cap;
  
  struct edge{
    int to,rev;
    Cap cap;
    
    edge(int _to,Cap _cap,int _rev):
      to(_to),rev(_rev),cap(_cap){};
  };
  
  vector<vector<edge> > G;  
  vector<int> iter,level;
  
  void add_edge(int from,int to,Cap cap){
    G[from].push_back(edge(to,cap,G[to].size()));
    G[to].push_back(edge(from,0,G[from].size()-1));
  }
  
  FlowGraphD(int V):G(V),iter(V),level(V){};
 
  void bfs(int s){
    fill(level.begin(),level.end(),-1);
    queue<pair<int,int> > q;
    q.push(make_pair(s,0));
    
    while(!q.empty()){
      int cv = q.front().first;
      int cc = q.front().second;
      q.pop();
      if(level[cv] != -1) continue;
      level[cv] = cc;
      for(int i = 0; i < (int)G[cv].size(); ++i){
        edge& e = G[cv][i];
        if(e.cap > 0 && level[e.to] == -1)
          q.push(make_pair(e.to,cc+1));
      }
    }
  }
  
  Cap dfs(int v,int t,Cap f){
    if(v == t)
      return f;
    
    for(int& i = iter[v]; i < (int)G[v].size(); ++i){
      edge& e = G[v][i];
      if(e.cap > 0 && level[v] < level[e.to]){
        Cap 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;
  }
  
  Cap max_flow(int s, int t){
    Cap flow = 0;
    // ll sum = 0;
    // for(int i = 0; i < (int)G[s].size(); ++i)
    //   sum += G[s][i].cap;
    
    for(;;){
      bfs(s);
      if(level[t] < 0) break;
      fill(iter.begin(), iter.end(), 0);
      Cap f;
      while((f = dfs(s, t,1LL << 30LL)) > 0){
        flow += f;
        //sum -= f;
      }
    }
    return flow;
  }
};


int main(int argc, char *argv[])
{
  int w,n;
  cin >> w >> n;
  vector<int> J(n);
  rep(j,n) cin >> J[j];

  int m;
  cin >> m;
  FlowGraphD fg(n+m+2);
  int source = n+m;
  int target = source+1;
  
  rep(j,n) fg.add_edge(source,j,J[j]);
  
  rep(j,m){
    int c;
    cin >> c;
    fg.add_edge(j+n,target,c);
  }
  
  rep(i,m){
    int qi;
    cin >> qi;
    set<int> app;
    rep(j,qi){
      int x;
      cin >> x;
      --x;
      app.insert(x);
    }
    rep(j,n) if(!app.count(j)) fg.add_edge(j,i+n,w);
  }
  auto now_w = fg.max_flow(source,target);
  //cout << "now_w" << "=" << now_w << endl;
  cout << (now_w>=w?"SHIROBAKO":"BANSAKUTSUKITA") << endl;
  
  return 0;
}
0