結果

問題 No.177 制作進行の宮森あおいです！
コンテスト
ユーザー rickytheta
提出日時 2015-12-16 21:34:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 1,812 bytes
コンパイル時間 1,866 ms
コンパイル使用メモリ 165,772 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 05:57:30
合計ジャッジ時間 2,377 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void add_edge(int, int, int)’:
main.cpp:29:45: warning: narrowing conversion of ‘g[to].std::vector<edge>::size()’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   29 |   g[from].push_back((edge){to,cap,g[to].size()});
      |                                   ~~~~~~~~~~^~
main.cpp:30:47: warning: narrowing conversion of ‘(g[from].std::vector<edge>::size() - 1)’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   30 |   g[to].push_back((edge){from,0,g[from].size()-1});
      |                                 ~~~~~~~~~~~~~~^~

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

#define V_MAX 110

struct edge{int to,cap,rev;};
vector<edge> g[V_MAX];
bool used[V_MAX];

void add_edge(int from,int to,int cap){
  g[from].push_back((edge){to,cap,g[to].size()});
  g[to].push_back((edge){from,0,g[from].size()-1});
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  used[v]=true;
  REP(i,g[v].size()){
    edge &e = g[v][i];
    if(!used[e.to]&&e.cap>0){
      int 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;
}

int ford_fulkerson(int s,int t){
  int flow = 0;
  while(true){
    REP(i,V_MAX)used[i]=false;
    int f = dfs(s,t,1e9);
    if(f==0)break;
    flow += f;
  }
  return flow;
}

int main(){
  int w,n;
  cin>>w>>n;
  vi j(n); REP(i,n)cin>>j[i];
  int m;
  cin>>m;
  vi c(m); REP(i,m)cin>>c[i];
  vector<vi> G(n,vi(m,1));
  REP(i,m){
    int q;
    cin>>q;
    REP(_,q){
      int x;
      cin>>x;
      G[x-1][i] = 0;
    }
  }

  // s: n+m
  // t: n+m+1
  // genga: 0~n-1
  // sakuga: n~n+m-1
  REP(i,n) add_edge(n+m,i,j[i]);
  REP(i,m) add_edge(n+i,n+m+1,c[i]);
  REP(i,n)REP(j,m){
    if(G[i][j]==0)continue;
    add_edge(i,n+j,1e9);
  }
  int f = ford_fulkerson(n+m,n+m+1);
  cout << (f>=w?"SHIROBAKO":"BANSAKUTSUKITA") << endl;
  return 0;
}
0