結果

問題 No.177 制作進行の宮森あおいです！
ユーザー PachicobuePachicobue
提出日時 2018-11-21 01:55:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 2,787 bytes
コンパイル時間 2,349 ms
コンパイル使用メモリ 213,016 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-24 15:52:40
合計ジャッジ時間 3,152 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 4 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 7 ms
5,248 KB
testcase_10 AC 10 ms
5,248 KB
testcase_11 AC 9 ms
5,248 KB
testcase_12 AC 8 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define show(x) std::cerr << #x << " = " << (x) << std::endl
template <typename T>
constexpr T INF = std::numeric_limits<T>::max() / 10;
class Flow
{
public:
    using T = int;
    struct Edge
    {
        std::size_t from, to, revind;
        T capacity, flow;
        bool reversed;
    };
    Flow(const std::size_t v) : V{v}, edge(v) {}
    void addEdge(const std::size_t from, const std::size_t to, const T capacity)
    {
        edge[from].push_back(Edge{from, to, (std::size_t)edge[to].size(), capacity, 0, false});
        edge[to].push_back(Edge{to, from, (std::size_t)edge[from].size() - 1, capacity, capacity, true});
    }
    T FordFulkerson(const std::size_t s, const std::size_t t)
    {
        std::vector<bool> checked(V);
        auto dfs = [&](auto&& self, const std::size_t pos, const T& flow) -> T {
            if (pos == t) { return flow; }
            checked[pos] = true;
            for (auto& e : edge[pos]) {
                if (checked[e.to]) { continue; }
                const T res = e.capacity - e.flow;
                if (res <= 0) { continue; }
                const T d = self(self, e.to, std::min(flow, res));
                if (d <= 0) { continue; }
                e.flow += std::min(d, res), edge[e.to][e.revind].flow -= std::min(d, res);
                return d;
            }
            return 0;
        };
        T flow = 0;
        while (true) {
            fill(checked.begin(), checked.end(), false);
            const T f = dfs(dfs, s, INF<T>);
            if (f == 0) { break; }
            flow += f;
        }
        return flow;
    }
    const std::size_t V;
    std::vector<std::vector<Edge>> edge;
};
template <typename T, typename A>
std::ostream& operator<<(std::ostream& os, const std::vector<T, A>& v)
{
    os << "[";
    for (const auto& p : v) { os << p << ","; }
    return (os << "]\n");
}
int main()
{
    int W, N;
    std::cin >> W >> N;
    std::vector<int> J(N);
    for (int i = 0; i < N; i++) { std::cin >> J[i]; }
    int M;
    std::cin >> M;
    std::vector<int> C(M);
    for (int i = 0; i < M; i++) { std::cin >> C[i]; }
    std::vector<std::vector<bool>> ok(N, std::vector<bool>(M, true));
    for (int i = 0, Q; i < M; i++) {
        std::cin >> Q;
        for (int j = 0, X; j < Q; j++) { std::cin >> X, ok[Q - 1][i] = false; }
    }
    Flow f(N + M + 2);
    const int S = N + M, T = N + M + 1;
    for (int i = 0; i < N; i++) { f.addEdge(S, i, J[i]); }
    for (int i = 0; i < M; i++) { f.addEdge(N + i, T, C[i]); }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (ok[i][j]) { f.addEdge(i, N + j, J[i]); }
        }
    }
    std::cout << (f.FordFulkerson(S, T) >= W ? "SHIROBAKO" : "BANSAKUTSUKITA") << std::endl;
    return 0;
}
0