#698624 (C++17) No.1678 Coin Trade (Multiple)

• 問題: No.1678 Coin Trade (Multiple)
• ユーザー: yuto1115
• 提出日時: 2021-09-10 23:29:58
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 721 ms / 5,000 ms
• コード長: 10,508 bytes
• コンパイル時間: 4,303 ms
• コンパイル使用メモリ: 228,028 KB
• 実行使用メモリ: 15,752 KB
• 最終ジャッジ日時: 2023-09-02 22:22:33
• 合計ジャッジ時間: 14,446 ms
• ジャッジサーバーID （参考情報）: judge11 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,368 KB
testcase_01	AC	2 ms; 4,368 KB
testcase_02	AC	1 ms; 4,368 KB
testcase_03	AC	45 ms; 8,424 KB
testcase_04	AC	241 ms; 12,332 KB
testcase_05	AC	109 ms; 14,416 KB
testcase_06	AC	85 ms; 13,300 KB
testcase_07	AC	198 ms; 9,448 KB
testcase_08	AC	134 ms; 10,060 KB
testcase_09	AC	121 ms; 14,440 KB
testcase_10	AC	42 ms; 5,612 KB
testcase_11	AC	176 ms; 11,804 KB
testcase_12	AC	35 ms; 5,532 KB
testcase_13	AC	404 ms; 13,800 KB
testcase_14	AC	109 ms; 8,332 KB
testcase_15	AC	135 ms; 11,380 KB
testcase_16	AC	43 ms; 11,384 KB
testcase_17	AC	129 ms; 14,660 KB
testcase_18	AC	2 ms; 4,372 KB
testcase_19	AC	2 ms; 4,372 KB
testcase_20	AC	2 ms; 4,368 KB
testcase_21	AC	2 ms; 4,368 KB
testcase_22	AC	1 ms; 4,368 KB
testcase_23	AC	1 ms; 4,372 KB
testcase_24	AC	2 ms; 4,372 KB
testcase_25	AC	2 ms; 4,372 KB
testcase_26	AC	2 ms; 4,368 KB
testcase_27	AC	2 ms; 4,372 KB
testcase_28	AC	2 ms; 4,372 KB
testcase_29	AC	1 ms; 4,368 KB
testcase_30	AC	1 ms; 4,368 KB
testcase_31	AC	2 ms; 4,376 KB
testcase_32	AC	1 ms; 4,372 KB
testcase_33	AC	2 ms; 4,372 KB
testcase_34	AC	2 ms; 4,372 KB
testcase_35	AC	2 ms; 4,372 KB
testcase_36	AC	1 ms; 4,368 KB
testcase_37	AC	2 ms; 4,372 KB
testcase_38	AC	2 ms; 4,368 KB
testcase_39	AC	1 ms; 4,372 KB
testcase_40	AC	2 ms; 4,368 KB
testcase_41	AC	2 ms; 4,368 KB
testcase_42	AC	2 ms; 4,368 KB
testcase_43	AC	2 ms; 4,372 KB
testcase_44	AC	2 ms; 4,372 KB
testcase_45	AC	2 ms; 4,368 KB
testcase_46	AC	2 ms; 4,368 KB
testcase_47	AC	2 ms; 4,372 KB
testcase_48	AC	518 ms; 14,908 KB
testcase_49	AC	510 ms; 14,996 KB
testcase_50	AC	514 ms; 15,000 KB
testcase_51	AC	526 ms; 15,004 KB
testcase_52	AC	520 ms; 14,940 KB
testcase_53	AC	721 ms; 14,880 KB
testcase_54	AC	520 ms; 14,796 KB
testcase_55	AC	523 ms; 14,792 KB
testcase_56	AC	528 ms; 14,792 KB
testcase_57	AC	508 ms; 14,860 KB
testcase_58	AC	332 ms; 15,752 KB

ソースコード

#include<bits/stdc++.h>
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d)
#define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--)
#define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--)
#define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d)
#define rrep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SUM(a) accumulate(all(a),0LL)
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SZ(a) int(a.size())
#define popcount(x) __builtin_popcountll(x)
#define pf push_front
#define pb push_back
#define ef emplace_front
#define eb emplace_back
#define ppf pop_front
#define ppb pop_back
#ifdef __LOCAL
#define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; }
#else
#define debug(...) void(0);
#endif
#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vp = vector<P>;
using vvp = vector<vp>;

template<class S, class T>
istream &operator>>(istream &is, pair<S, T> &p) { return is >> p.first >> p.second; }

template<class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << '{' << p.first << ", " << p.second << '}'; }

template<class S, class T, class U>
istream &operator>>(istream &is, tuple<S, T, U> &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); }

template<class S, class T, class U>
ostream &operator<<(ostream &os, const tuple<S, T, U> &t) {
    return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}';
}

template<class T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T &t : v) { is >> t; }
    return is;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << '[';
    rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", ");
    return os << ']';
}

template<class T>
ostream &operator<<(ostream &os, const set<T> &st) {
    os << '{';
    auto it = st.begin();
    while (it != st.end()) {
        os << (it == st.begin() ? "" : ", ") << *it;
        it++;
    }
    return os << '}';
}

template<class T>
void vecout(const vector<T> &v, char div = '\n') {
    rep(i, v.size()) cout << v[i] << (i == int(v.size() - 1) ? '\n' : div);
}

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

void scan() {}

template<class Head, class... Tail>
void scan(Head &head, Tail &... tail) {
    cin >> head;
    scan(tail...);
}

template<class T>
void print(const T &t) { cout << t << '\n'; }

template<class Head, class... Tail>
void print(const Head &head, const Tail &... tail) {
    cout << head << ' ';
    print(tail...);
}

template<class... T>
void fin(const T &... a) {
    print(a...);
    exit(0);
}

struct Init_io {
    Init_io() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        cout << boolalpha << fixed << setprecision(15);
        cerr << boolalpha << fixed << setprecision(15);
    }
} init_io;

const string yes[] = {"no", "yes"};
const string Yes[] = {"No", "Yes"};
const string YES[] = {"NO", "YES"};
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T, class S>
vector<T> cumsum(const vector<S> &v, bool shift_one = true) {
    int n = v.size();
    vector<T> res;
    if (shift_one) {
        res.resize(n + 1);
        rep(i, n) res[i + 1] = res[i] + v[i];
    } else {
        res.resize(n);
        if (n) {
            res[0] = v[0];
            rep(i, 1, n) res[i] = res[i - 1] + v[i];
        }
    }
    return res;
}

vvi graph(int n, int m, bool directed = false, int origin = 1) {
    vvi G(n);
    rep(_, m) {
        INT(u, v);
        u -= origin, v -= origin;
        G[u].pb(v);
        if (!directed) G[v].pb(u);
    }
    return G;
}

template<class T>
vector<vector<pair<int, T>>> weighted_graph(int n, int m, bool directed = false, int origin = 1) {
    vector<vector<pair<int, T>>> G(n);
    rep(_, m) {
        int u, v;
        T w;
        scan(u, v, w);
        u -= origin, v -= origin;
        G[u].eb(v, w);
        if (!directed) G[v].eb(u, w);
    }
    return G;
}

template<class Cap, class Cost>
class MCF {
    struct _edge {
        int to, rev;
        Cap cap;
        Cost cost;
        
        _edge(int to, int rev, Cap cap, Cost cost) : to(to), rev(rev), cap(cap), cost(cost) {}
    };
    
    int n;
    vp pos;
    vector<vector<_edge>> G;

public:
    explicit MCF(int n) : n(n), G(n) {}
    
    int add_edge(int from, int to, Cap cap, Cost cost) {
        assert(0 <= from and from < n);
        assert(0 <= to and to < n);
        assert(from != to);
        pos.eb(from, G[from].size());
        G[from].eb(to, G[to].size(), cap, cost);
        G[to].eb(from, G[from].size() - 1, 0, -cost);
        return pos.size() - 1;
    }
    
    struct edge {
        int from, to;
        Cap cap, flow;
        Cost cost;
        
        edge(int from, int to, Cap cap, Cap flow, Cost cost) : from(from), to(to), cap(cap), flow(flow), cost(cost) {}
    };
    
    edge get_edge(int i) {
        assert(0 <= i && i < int(pos.size()));
        auto e = G[pos[i].first][pos[i].second];
        auto re = G[e.to][e.rev];
        return edge(pos[i].first, e.to, e.cap + re.cap, re.cap, e.cost);
    }
    
    vector<edge> edges() {
        int m = pos.size();
        vector<edge> res(m);
        rep(i, m) res[i] = get_edge(i);
        return res;
    }
    
    pair<Cap, Cost> flow(int s, int t) {
        return flow(s, t, numeric_limits<Cap>::max());
    }
    
    pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {
        return slope(s, t, flow_limit).back();
    }
    
    vector<std::pair<Cap, Cost>> slope(int s, int t) {
        return slope(s, t, numeric_limits<Cap>::max());
    }
    
    // this must not be called more than once
    // O(F (E + V) log V)
    vector<pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
        assert(0 <= s and s < n);
        assert(0 <= t and t < n);
        assert(s != t);
        // variants (C = maxcost):
        // -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0
        // reduced cost (= e.cost + dual[e.from] - dual[e.to]) >= 0 for all _edge
        vector<Cost> dual(n, 0), dist(n);
        vi pv(n), pe(n);
        vb seen(n);
        auto dual_ref = [&]() -> bool {
            fill(all(dist), numeric_limits<Cost>::max());
            fill(all(pv), -1);
            fill(all(pe), -1);
            fill(all(seen), false);
            priority_queue<pair<Cost, int>, vector<pair<Cost, int>>, greater<pair<Cost, int>>> q;
            dist[s] = 0;
            q.emplace(0, s);
            while (not q.empty()) {
                int u = q.top().second;
                q.pop();
                if (seen[u]) continue;
                seen[u] = true;
                if (u == t) break;
                // dist[u] = shortest(s, u) + dual[s] - dual[u]
                // dist[u] >= 0 (all reduced cost are positive)
                // dist[u] <= (n-1)C
                rep(i, G[u].size()) {
                    auto e = G[u][i];
                    if (seen[e.to] or !e.cap) continue;
                    // |-dual[e.to] + dual[u]| <= (n-1)C
                    // cost <= C - -(n-1)C + 0 = nC
                    Cost cost = e.cost - dual[e.to] + dual[u];
                    if (chmin(dist[e.to], dist[u] + cost)) {
                        pv[e.to] = u;
                        pe[e.to] = i;
                        q.emplace(dist[e.to], e.to);
                    }
                }
            }
            if (!seen[t]) {
                return false;
            }
            
            rep(u, n) {
                if (!seen[u]) continue;
                // dual[u] = dual[u] - dist[t] + dist[u]
                //         = dual[u] - (shortest(s, t) + dual[s] - dual[t]) + (shortest(s, u) + dual[s] - dual[u])
                //         = - shortest(s, t) + dual[t] + shortest(s, v)
                //         = shortest(s, v) - shortest(s, t) >= 0 - (n-1)C
                dual[u] -= dist[t] - dist[u];
            }
            return true;
        };
        Cap flow = 0;
        Cost cost = 0, prev_cost_per_flow = -1;
        vector<pair<Cap, Cost>> res;
        res.eb(flow, cost);
        while (flow < flow_limit) {
            if (!dual_ref()) break;
            Cap c = flow_limit - flow;
            for (int u = t; u != s; u = pv[u]) {
                chmin(c, G[pv[u]][pe[u]].cap);
            }
            for (int u = t; u != s; u = pv[u]) {
                auto &e = G[pv[u]][pe[u]];
                e.cap -= c;
                G[u][e.rev].cap += c;
            }
            Cost d = -dual[s];
            flow += c;
            cost += c * d;
            if (prev_cost_per_flow == d) {
                res.pop_back();
            }
            res.eb(flow, cost);
            prev_cost_per_flow = d;
        }
        return res;
    }
    
};

int main() {
    INT(n, k);
    vi a(n), m(n);
    vvi b(n);
    rep(i, n) {
        scan(a[i], m[i]);
        b[i].resize(m[i]);
        scan(b[i]);
        for (int &j : b[i]) --j;
    }
    MCF<int, ll> mcf(n);
    ll mx = 1000000000;
    rep(i, n - 1) mcf.add_edge(i, i + 1, inf, mx);
    rep(i, n) {
        for (int j : b[i]) {
            if (a[j] > a[i]) continue;
            mcf.add_edge(j, i, 1, mx * (i - j) - (a[i] - a[j]));
        }
    }
    fin(mx * (n - 1) * k - mcf.flow(0, n - 1, k).second);
}