結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー |
![]() |
提出日時 | 2022-05-25 13:53:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 4,132 bytes |
コンパイル時間 | 2,266 ms |
コンパイル使用メモリ | 207,316 KB |
最終ジャッジ日時 | 2025-01-29 15:16:27 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
#include <bits/stdc++.h>using namespace std;// #include<atcoder/all>// using namespace atcoder;using ll = long long;template<class T> using V = std::vector<T>;#define REP(i, n) for (ll i=(ll)0; i<(ll)(n); i++)#define REPS(i, s, n) for (ll i=(ll)(s); i<(ll)(n); i++)#define RREP(i, n) for (ll i=(ll)(n); i>(ll)0; i--)#define RREPS(i, s, n) for (ll i=(ll)(n); i>(ll)(s); i--)#define ALL(c) std::begin((c)), std::end((c))struct io {io() {cin.tie(0); ios::sync_with_stdio(0);} } caller;template<typename T>struct DinicCapacityScaling{static_assert(is_integral<T>::value, "template parameter T must be integral type");private:const T INF;struct edge{int to;T cap;int rev;bool isrev;int idx;};vector<vector<edge>> graph;vector<int> min_cost, iter;T max_cap;bool build_augment_path(int s, int t, const T &base){min_cost.assign(graph.size(), -1);queue<int> que;min_cost[s] = 0;que.push(s);while (!que.empty() && min_cost[t] == -1){int p = que.front();que.pop();for (auto &e : graph[p]){if (e.cap >= base && min_cost[e.to] == -1){min_cost[e.to] = min_cost[p] + 1;que.push(e.to);}}}return min_cost[t] != -1;}T find_augment_path(int idx, const int t, T base, T flow){if (idx == t) return flow;T sum = 0;for(int &i = iter[idx]; i < (int)graph[idx].size(); i++){edge &e = graph[idx][i];if (e.cap >= base && min_cost[idx] < min_cost[e.to]){T d = find_augment_path(e.to, t, base, min(flow - sum, e.cap));if (d > 0){e.cap -= d;graph[e.to][e.rev].cap += d;sum += d;if (flow - sum < base) break;}}}return sum;}public:explicit DinicCapacityScaling(int V) : INF(numeric_limits<T>::max()), graph(V), max_cap(0) {}void add_edge(int from, int to, T cap, int idx = -1){max_cap = max(max_cap, cap);graph[from].emplace_back((edge){to, cap, (int)graph[to].size(), false, idx});graph[to].emplace_back((edge){from, 0, (int)graph[from].size() - 1, true, idx});}T max_flow(int s, int t){if (max_cap == T(0)) return T(0);T flow = 0;for (int i = 63 - __builtin_clzll(max_cap); i >= 0; i--){T now = T(1) << i;while (build_augment_path(s, t, now)){iter.assign(graph.size(), 0);flow += find_augment_path(s, t, now, INF);}}return flow;}void output(){for (int i = 0; i < (int)graph.size(); i++){for (auto &e : graph[i]){if (e.isrev) continue;auto &rev_e = graph[e.to][e.rev];cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;}}}};int main(){int w, n, m;cin >> w >> n;V<int> j(n);REP (i, n) cin >> j[i];cin >> m;V<int> c(m);REP (i, m) cin >> c[i];DinicCapacityScaling<int> mf(n + m + 2);REP (i, n) mf.add_edge(n + m, i, j[i]);REP (i, m) mf.add_edge(i + n, n + m + 1, c[i]);int q;REP (i, m){cin >> q;V<int> x(q);REP (j, q) cin >> x[j];REP (j, n){if (!binary_search(ALL(x), j + 1)){mf.add_edge(j, i + n, c[i]);}}}if (mf.max_flow(n + m, n + m + 1) >= w) cout << "SHIROBAKO" << endl;else cout << "BANSAKUTSUKITA" << endl;return 0;}