結果

問題 No.177 制作進行の宮森あおいです！
ユーザー eggkid6eggkid6
提出日時 2023-11-14 20:11:20
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 5,698 bytes
コンパイル時間 2,805 ms
コンパイル使用メモリ 221,868 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2023-11-14 20:11:24
合計ジャッジ時間 3,520 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < ll(n); ++i)
#define per(i, n) for (ll i = ll(n) - 1; i >= 0; --i)
#define per2(i, s, n) for (ll i = ll(n) - 1; i >= s; --i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define fi first
#define se second
#define pf push_front
#define pb push_back
#define ppf pop_front
#define ppb pop_back
#define ef emplace_front
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define fix(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<ll>;
using P = pair<ll,ll>;
using M = map<ll,ll>;
using S = set<ll>;
using Q = queue<ll>;
using PQ = priority_queue<ll>;
using VV = vector<V>;
using VVV = vector<VV>;
using VVVV = vector<VVV>;
using VVVVV = vector<VVVV>;
using VVVVVV = vector<VVVVV>;
using VS = vector<string>;
using VP = vector<P>;
using VB = vector<bool>;
template<class T>
using PQG = priority_queue<T, vector<T>, greater<T>>;
template<class T>
bool constexpr chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
bool constexpr chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
void constexpr Vin(vector<T> &v) {
    for (T &a : v) cin >> a;
}
template<class T>
void constexpr Vout(vector<T> &v) {
    for (T &a : v) cout << a << " ";
    cout << endl;
}
template<class T>
void constexpr Voutl(vector<T> &v) {
    for (T &a : v) cout << a << endl;
}
const ll power(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
const ll mpower(ll a, ll b, const ll &m) {
    a %= m;
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
const string yes[] = {"no", "yes"};
const string Yes[] = {"No", "Yes"};
const string YES[] = {"NO", "YES"};
const int H[] = {1, 0, -1, 0};
const int W[] = {0, 1, 0, -1};
constexpr ll mod = 998244353;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1LL << 60;

template <class T>
struct MaximumFlow {
    struct Edge {
        int to, rev;
        T cap;
        Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap) {}
    };
    struct edge {
        int from, to;
        T cap, flow;
        edge(int from, int to, T cap, T flow) : from(from), to(to), cap(cap), flow(flow) {}
    };
    int n;
    vector<vector<Edge>> G;
    vector<int> level, iter;
    vector<pair<int,int>> pos;
    queue<int> q;
    MaximumFlow() : n(0) {}
    MaximumFlow(int n) : n(n), G(n), level(n), iter(n) {}
    void add_edge(int from, int to, T cap) {
        int from_id = G[from].size();
        int to_id = G[to].size() + (from == to);
        pos.emplace_back(from, from_id);
        G[from].emplace_back(to, to_id, cap);
        G[to].emplace_back(from, from_id, 0);
    }
    T dfs(int v, int t, T up) {
        if (v == t) return up;
        T res = 0;
        for (int& i = iter[v]; i < int(G[v].size()); ++i) {
            Edge& e = G[v][i];
            if (level[v] >= level[e.to] || e.cap == 0) continue;
            T f = dfs(e.to, t, min(up - res, e.cap));
            if (f == 0) continue;
            e.cap -= f;
            G[e.to][e.rev].cap += f;
            res += f;
            if (res == up) return res;
        }
        return res;
    }
    T flow(int s, int t) {
        return flow(s, t, numeric_limits<T>::max());
    }
    T flow(int s, int t, T flow_limit) {
        T flow = 0;
        while (true) {
            fill(level.begin(), level.end(), -1);
            q.push(s);
            level[s] = 0;
            while (q.size()) {
                int v = q.front();
                q.pop();
                for (Edge& e : G[v]) {
                    if (level[e.to] != -1 || e.cap == 0) continue;
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
            if (level[t] == -1) return flow;
            fill(iter.begin(), iter.end(), 0);
            T f = dfs(s, t, flow_limit - flow);
            if (f == 0) return flow;
            flow += f;
        }
    }
    edge get_edge(int i) {
        Edge& e = G[pos[i].first][pos[i].second];
        Edge& re = G[e.to][e.rev];
        return edge{pos[i].first, e.to, e.cap + re.cap, re.cap};
    }
    vector<edge> edges() {
        vector<edge> res;
        for (int i = 0; i < int(pos.size()); ++i) {
            res.push_back(get_edge(i));
        }
        return res;
    }
    vector<bool> min_cut(int s) {
        vector<bool> res(n);
        q.push(s);
        res[s] = true;
        while (q.size()) {
            int v = q.front();
            q.pop();
            for (Edge& e : G[v]) {
                if (e.cap && !res[e.to]) {
                    res[e.to] = true;
                    q.push(e.to);
                }
            }
        }
        return res;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll w, n;
    cin >> w >> n;
    V j(n);
    Vin(j);
    ll m;
    cin >> m;
    V c(m);
    Vin(c);
    MaximumFlow<ll> mf(n + m + 2);
    ll s = n + m, t = n + m + 1;
    rep(i, n) mf.add_edge(s, i, j[i]);
    rep(i, m) mf.add_edge(n + i, t, c[i]);
    rep(i, m) {
        ll q;
        cin >> q;
        VB b(n);
        rep(j, q) {
            ll x;
            cin >> x;
            b[x - 1] = true;
        }
        rep(j, n) if (!b[j]) mf.add_edge(j, n + i, INF);
    }
    if (mf.flow(s, t) >= w) cout << "SHIROBAKO\n";
    else cout << "BANSAKUTSUKITA\n";
}
0