結果

問題 No.177 制作進行の宮森あおいです！
ユーザー vain0vain0
提出日時 2015-06-01 19:05:59
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 2,562 bytes
コンパイル時間 812 ms
コンパイル使用メモリ 84,608 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 13:16:22
合計ジャッジ時間 1,481 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 4 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 9 ms
6,940 KB
testcase_10 AC 13 ms
6,940 KB
testcase_11 AC 11 ms
6,940 KB
testcase_12 AC 7 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void add_edge(int, int, int)’:
main.cpp:49:61: warning: narrowing conversion of ‘graph[to].std::vector<edge>::size()’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   49 |         graph[from].push_back(edge { to, cap, graph[to].size() });
      |                                               ~~~~~~~~~~~~~~^~
main.cpp:50:64: warning: narrowing conversion of ‘(graph[from].std::vector<edge>::size() - 1)’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   50 |         graph[to].push_back(edge { from, 0, graph[from].size() - 1 });
      |                                             ~~~~~~~~~~~~~~~~~~~^~~

ソースコード

diff # 

#include <cassert>
#include <functional>
#include <set>
#include <ctime>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
#ifndef ONLINE_JUDGE //POJ
# include <random>
# include <array>
# define mkt make_tuple
# define empb emplace_back
#endif
#ifdef _LOCAL
# include "for_local.h"
#endif
using namespace std;
typedef unsigned int uint; typedef unsigned long long ull;
#define repi(_I, _B, _E) for(int _I = (_B); (_I) < (_E); ++ (_I))
#define rep(_I, _N) for(int _I = 0; (_I) < (_N); ++ (_I))
#define mkp make_pair
#define all(_X) (_X).begin(), (_X).end()
#define scani(_V) std::scanf("%d", &_V)
#define printi(_V) std::printf("%d", static_cast<int>(_V))

//みゃーもり(0)→原画たち(2+i)→作監たち(2+n+j)→終点(2)、というDAG
//みゃーもり→原画、へはその原画が描ける枚数まで流せる
//原画と作監の間は K_n,m から「合わない組み合わせ」を取り除いたもの。ここでは任意枚の原画を流せる。
//作監→終点、へはその作監が仕上げられる枚数まで流せる
//Wカット以上流せれば万策尽きない

int const INF = 1<<29;
int const MAX_V = 2 + 50 + 50;

//蟻本p190の改変
#if 1
struct edge { int to, cap, rev; };
vector<edge> graph[MAX_V];
bool used[MAX_V];
void add_edge(int from, int to, int cap) {
	graph[from].push_back(edge { to, cap, graph[to].size() });
	graph[to].push_back(edge { from, 0, graph[from].size() - 1 });
}
int dfs(int v, int t, int f) {
	if ( v == t ) return f;
	used[v] = true;
	rep(i, graph[v].size()) {
		edge& e = graph[v][i];
		if ( !used[e.to] && e.cap > 0 ) {
			int const d = dfs(e.to, t, min(f, e.cap));
			if ( d > 0 ) {
				e.cap -= d;
				graph[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s, int t) {
	int flow = 0;
	for ( ;; ) {
		memset(used, 0, sizeof(used));
		int const f = dfs(s, t, INF);
		if ( f == 0 ) return flow;
		flow += f;
	}
}
#endif

int w, n, m;
signed main() {
	cin >> w >> n;
	rep(i, n) {
		int j; cin >> j;
		add_edge(0, 2 + i, j);
	}
	cin >> m;
	rep(i, m) {
		int c; cin >> c;
		add_edge(2 + n + i, 1, c);
	}
	rep(i, m) {
		int qi; cin >> qi;
		vector<bool> js(n, true);
		rep(j, qi) {
			int k;
			cin >> k; --k;
			js[k] = false;
		}
		rep(k, n) {
			if ( js[k] ) {
				add_edge(2 + k, 2 + n + i, INF);
			}
		}
	}

	int const max_w = max_flow(0, 1);
	cout << (max_w >= w ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl;

	return 0;
}
0