結果

問題 No.177 制作進行の宮森あおいです！
ユーザー yuustiyuusti
提出日時 2015-04-02 23:32:11
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,923 bytes
コンパイル時間 1,055 ms
コンパイル使用メモリ 106,820 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-04 01:27:24
合計ジャッジ時間 1,677 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <climits>
#include <bitset>
#include <cassert>
#include <unordered_map>

#ifdef _MSC_VER
#include <agents.h>
#endif

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end())
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;

class MaxFlow{
	struct edge{
		int to, rev, cap;
		edge(){}
		edge(int to, int rev, int cap) :to(to), rev(rev), cap(cap){}
	};
	vector<vector<edge> > Graph;
	vector<int> used, level, iter;
	int V;
	static const int INF = 1 << 30;
public:
	MaxFlow(int size) :V(size){
		Graph.resize(V);
		iter.resize(V, 0);
		level.resize(V);
		used.resize(V, 0);
	}
	void add(int from, int to, int cap){
		Graph[from].push_back(edge(to, Graph[to].size(), cap));
		Graph[to].push_back(edge(from, Graph[from].size() - 1, 0));
	}

	void dinic_bfs(int s){
		fill(level.begin(), level.end(), -1);

		queue<int> q;
		q.push(s);
		level[s] = 0;
		while (!q.empty()){
			int v = q.front(); q.pop();
			for (int i = 0; i < Graph[v].size(); i++){
				edge &e = Graph[v][i];
				if (e.cap <= 0 || level[e.to] >= 0) continue;
				level[e.to] = level[v] + 1;
				q.push(e.to);
			}
		}
	}

	int dinic_dfs(int s, int t, int f){
		if (s == t) return f;
		for (int &i = iter[s]; i < Graph[s].size(); i++){
			edge &e = Graph[s][i];
			if (e.cap <= 0 || level[e.to] <= level[s]) continue;
			int res = dinic_dfs(e.to, t, min(f, e.cap));
			if (res > 0){
				e.cap -= res;
				Graph[e.to][e.rev].cap += res;
				return res;
			}
		}
		return 0;
	}

	int dinic(int s, int t){
		int res = 0;
		while (1){
			dinic_bfs(s);
			if (level[t] < 0) break;
			fill(iter.begin(), iter.end(), 0);
			int f;
			while (f = dinic_dfs(s, t, INF)){
				res += f;
			}
		}
		return res;
	}

	int max_flow(int s, int t){
		return dinic(s, t);
	}
};



int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout.setf(ios::fixed);
	cout.precision(20);

	int w, n, m;
	cin >> w >> n;
	MaxFlow mf(102);

	const int SRC = 100, SNK = SRC + 1;
	rep(i, n){
		int c;
		cin >> c;
		mf.add(SRC, i, c);
	}
	cin >> m;
	rep(i, m){
		int c;
		cin >> c;
		mf.add(n + i, SNK, c);
	}

	rep(i, m){
		int q;
		cin >> q;
		set<int> st;
		rep(i, q){
			int x;
			cin >> x;
			st.insert(x-1);
		}
		rep(j, n){
			if (st.count(j)) continue;
			mf.add(j, n + i, w);
		}
	}

	bool ok = mf.max_flow(SRC, SNK) >= w;

	cout << (ok ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl;
}
0