結果

問題 No.177 制作進行の宮森あおいです！
ユーザー sugim48sugim48
提出日時 2015-04-02 23:39:45
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 2,212 bytes
コンパイル時間 816 ms
コンパイル使用メモリ 92,616 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-17 03:46:05
合計ジャッジ時間 1,626 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 13 ms
4,376 KB
testcase_11 AC 3 ms
4,380 KB
testcase_12 AC 8 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘void flow_network::add_edge(int, int, ll)’:
main.cpp:40:28: warning: narrowing conversion of ‘(&((flow_network*)this)->flow_network::G.std::vector<std::vector<flow_network::edge> >::operator[](((std::vector<std::vector<flow_network::edge> >::size_type)v)))->std::vector<flow_network::edge>::size()’ from ‘std::vector<flow_network::edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ inside { } [-Wnarrowing]
   edge e = {v, c, G[v].size()}, _e = {u, 0, G[u].size()};
                   ~~~~~~~~~^~
main.cpp:40:54: warning: narrowing conversion of ‘(&((flow_network*)this)->flow_network::G.std::vector<std::vector<flow_network::edge> >::operator[](((std::vector<std::vector<flow_network::edge> >::size_type)u)))->std::vector<flow_network::edge>::size()’ from ‘std::vector<flow_network::edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ inside { } [-Wnarrowing]
   edge e = {v, c, G[v].size()}, _e = {u, 0, G[u].size()};
                                             ~~~~~~~~~^~

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

struct flow_network {
	int n;
	struct edge { int v; ll c; int rev; };
	vector< vector<edge> > G;
	flow_network(int _n) : n(_n), G(_n) {}
	void add_edge(int u, int v, ll c) {
		edge e = {v, c, G[v].size()}, _e = {u, 0, G[u].size()};
		G[u].push_back(e); G[v].push_back(_e);
	}
	ll dfs(int u, int t, ll f, vector<bool>& vis) {
		if (u == t) return f;
		vis[u] = true;
		for (int i = 0; i < G[u].size(); i++) {
			edge& e = G[u][i];
			if (vis[e.v] || e.c == 0) continue;
			ll d = min(e.c, dfs(e.v, t, min(f, e.c), vis));
			if (d == 0) continue;
			e.c -= d;
			G[e.v][e.rev].c += d;
			return d;
		}
		return 0;
	}
	ll max_flow(int s, int t) {
		ll res = 0;
		for (;;) {
			vector<bool> vis(n);
			ll f = dfs(s, t, LLONG_MAX, vis);
			if (f == 0) return res;
			res += f;
		}
	}
};

int main() {
	int W; cin >> W;
	int N; cin >> N;
	vector<int> J(N);
	for (int i = 0; i < N; i++)
		cin >> J[i];
	int M; cin >> M;
	vector<int> C(M);
	for (int j = 0; j < M; j++)
		cin >> C[j];
	vector<set<int> > X(M);
	for (int j = 0; j < M; j++) {
		int Q; cin >> Q;
		while (Q--) {
			int x; cin >> x;
			X[j].insert(x - 1);
		}
	}
	flow_network fn(N + M + 3);
	int s = N + M, t = N + M + 1, ss = N + M + 2;
	for (int i = 0; i < N; i++)
		fn.add_edge(s, i, J[i]);
	for (int j = 0; j < M; j++)
		fn.add_edge(N + j, t, C[j]);
	for (int j = 0; j < M; j++)
		for (int i = 0; i < N; i++) {
			if (X[j].count(i)) continue;
			fn.add_edge(i, N + j, 10000);
		}
	fn.add_edge(ss, s, W);
	int x = fn.max_flow(ss, t);
	cout << (x == W ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl;
}
0