結果
| 問題 | No.177 制作進行の宮森あおいです！ |
| ユーザー |
 lemondo
|
| 提出日時 | 2023-09-29 15:16:57 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 7,257 bytes |
| コンパイル時間 | 3,109 ms |
| コンパイル使用メモリ | 319,416 KB |
| 最終ジャッジ日時 | 2025-02-17 02:57:18 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
ソースコード
#pragma region Macros#include <bits/stdc++.h>#include <immintrin.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cctype>#include <cfenv>#include <cfloat>#include <chrono>#include <cinttypes>#include <climits>#include <cmath>#include <complex>#include <cstdarg>#include <cstddef>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <fstream>#include <functional>#include <initializer_list>#include <iomanip>#include <ios>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <streambuf>#include <string>#include <tuple>#include <type_traits>#include <typeinfo>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#define ll long long#define OVERLOAD(e1, e2, e3, e4, NAME, ...) NAME#define _rep1(i, n) for (long long i = 0; i < n; i++)#define _rep2(i, a, b) for (long long i = a; i < b; ++i)#define _rep3(i, a, b, t) \for (long long i = a; i * (t / abs(t)) < b * (t / abs(t)); i += t)#define rep(...) OVERLOAD(__VA_ARGS__, _rep3, _rep2, _rep1, _)(__VA_ARGS__)#define all(x) (x).begin(), (x).end()#define sz(x) (int)x.size()#define fi first#define se second#define pb push_back#define eb emplace_back#define mp make_pair#define pcnt __builtin_popcountll#define SORT(v) sort(all(v))#define UNIQUE(v) \SORT(v); \v.erase(unique(v.begin(), v.end()), v.end());#define COPY(A, B) copy(all(A), B.begin());#define REV(v) reverse(all(v))#define MAX(x) *max_element(all(x))#define MIN(x) *min_element(all(x))#ifdef LOCAL#define dbg(x) \{ \cout << __LINE__ << " : " << #x << " = "; \print(x); \}#define IS_LOCAL true#else#define dbg(x) true#define IS_LOCAL false#endifusing namespace std;template <typename T>using vc = vector<T>;template <typename T>using vvc = vector<vc<T>>;template <typename T>using vvvc = vector<vvc<T>>;template <typename T>bool chmin(T& k, T m) {bool ret = k > m;k = min(k, m);return ret;}template <typename T>bool chmax(T& k, T m) {bool ret = k < m;k = max(k, m);return ret;}template <typename T>inline void print(const vector<T>& v, string s = " ") {for (int i = 0; i < (int)v.size(); i++)cout << v[i] << (i != (int)v.size() - 1 ? s : "");cout << "\n";}template <typename T, typename S>inline void print(const pair<T, S>& p) {cout << p.first << " " << p.second << endl;}template <typename T>inline void print(const T& x) {cout << x << "\n";}template <typename T, typename S>inline void print(const vector<pair<T, S>>& v) {for (auto&& p : v) print(p);}void yes(bool a) { cout << (a ? "yes" : "no") << endl; }void YES(bool a) { cout << (a ? "YES" : "NO") << endl; }void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; }template <typename T>T SUM(vc<T> As) {T ret = 0;for (T a : As) ret += a;return ret;}#pragma endregionconst ll INF = numeric_limits<long long>::max();/*** @brief Dinic(最大流)* @docs docs/dinic.md*/template <typename flow_t>struct Dinic {const flow_t INF;struct edge {int to;flow_t cap;int rev;bool isrev;int idx;};vector<vector<edge>> graph;vector<int> min_cost, iter;explicit Dinic(int V) : INF(numeric_limits<flow_t>::max()), graph(V) {}void add_edge(int from, int to, flow_t cap, int idx = -1) {assert(cap >= 0);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});}bool build_augment_path(int s, int t) {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 > 0 && min_cost[e.to] == -1) {min_cost[e.to] = min_cost[p] + 1;que.push(e.to);}}}return min_cost[t] != -1;}flow_t find_min_dist_augment_path(int idx, const int t, flow_t flow) {if (idx == t) return flow;for (int& i = iter[idx]; i < (int)graph[idx].size(); i++) {edge& e = graph[idx][i];if (e.cap > 0 && min_cost[idx] < min_cost[e.to]) {flow_t d =find_min_dist_augment_path(e.to, t, min(flow, e.cap));if (d > 0) {e.cap -= d;graph[e.to][e.rev].cap += d;return d;}}}return 0;}flow_t max_flow(int s, int t) {flow_t flow = 0;while (build_augment_path(s, t)) {iter.assign(graph.size(), 0);flow_t f;while ((f = find_min_dist_augment_path(s, t, INF)) > 0) flow += f;}return flow;}void output() {for (int i = 0; i < 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;}}}vector<bool> min_cut(int s) {// 何に使うのこれ？vector<bool> used(graph.size());queue<int> que;que.emplace(s);used[s] = true;while (not que.empty()) {int p = que.front();que.pop();for (auto& e : graph[p]) {if (e.cap > 0 and not used[e.to]) {used[e.to] = true;que.emplace(e.to);}}}return used;}};void solve() {ll W;cin >> W;ll N;cin >> N;vc<ll> Js(N);rep(i, N) cin >> Js[i];ll M;cin >> M;vc<ll> Cs(M);rep(i, M) cin >> Cs[i];Dinic<ll> dinic(N + M + 2);rep(i, N) { dinic.add_edge(N + M, i, Js[i]); }rep(i, M) {ll Q;cin >> Q;unordered_set<ll> cant;rep(_, Q) {ll x;cin >> x;x--;cant.insert(x);}rep(j, N) {if (cant.count(j)) continue;dinic.add_edge(j, N + i, Js[j]);}dinic.add_edge(N + i, N + M + 1, Cs[i]);}ll f = dinic.max_flow(N + M, N + M + 1);dbg(f);if (f >= W) {print("SHIROBAKO");} else {print("BANSAKUTSUKITA");}}int main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);// ll T; cin >> T;// rep(_, T)solve();}