#938372 (C++17) No.1615 Double Down

提出ソース

結果

問題	No.1615 Double Down
ユーザー	tko919
提出日時	2023-12-15 05:29:10
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	955 ms / 10,000 ms
コード長	13,909 bytes
コンパイル時間	2,964 ms
コンパイル使用メモリ	236,992 KB
実行使用メモリ	21,504 KB
最終ジャッジ日時	2024-09-27 06:01:23
合計ジャッジ時間	24,182 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	363 ms 13,964 KB
testcase_01	AC	403 ms 13,836 KB
testcase_02	AC	526 ms 16,760 KB
testcase_03	AC	473 ms 16,628 KB
testcase_04	AC	439 ms 16,888 KB
testcase_05	AC	468 ms 16,760 KB
testcase_06	AC	606 ms 20,060 KB
testcase_07	AC	568 ms 21,504 KB
testcase_08	AC	591 ms 19,896 KB
testcase_09	AC	858 ms 17,016 KB
testcase_10	AC	829 ms 17,148 KB
testcase_11	AC	804 ms 17,144 KB
testcase_12	AC	557 ms 18,196 KB
testcase_13	AC	580 ms 18,212 KB
testcase_14	AC	547 ms 18,588 KB
testcase_15	AC	492 ms 19,812 KB
testcase_16	AC	536 ms 20,448 KB
testcase_17	AC	511 ms 19,444 KB
testcase_18	AC	861 ms 17,144 KB
testcase_19	AC	955 ms 17,076 KB
testcase_20	AC	928 ms 17,008 KB
testcase_21	AC	799 ms 17,148 KB
testcase_22	AC	830 ms 17,144 KB
testcase_23	AC	881 ms 17,148 KB
testcase_24	AC	823 ms 17,016 KB
testcase_25	AC	762 ms 17,016 KB
testcase_26	AC	784 ms 17,016 KB
testcase_27	AC	64 ms 7,600 KB
testcase_28	AC	71 ms 7,600 KB
testcase_29	AC	107 ms 8,888 KB
testcase_30	AC	110 ms 9,016 KB
testcase_31	AC	115 ms 8,888 KB
testcase_32	AC	113 ms 9,016 KB
testcase_33	AC	171 ms 10,436 KB
testcase_34	AC	168 ms 10,560 KB
testcase_35	AC	163 ms 10,560 KB
testcase_36	AC	5 ms 6,944 KB
testcase_37	AC	5 ms 6,940 KB
testcase_38	AC	7 ms 6,944 KB
testcase_39	AC	7 ms 6,944 KB
testcase_40	AC	7 ms 6,940 KB
testcase_41	AC	7 ms 6,940 KB
testcase_42	AC	9 ms 6,940 KB
testcase_43	AC	10 ms 6,940 KB
testcase_44	AC	9 ms 6,940 KB
testcase_45	AC	2 ms 6,940 KB
testcase_46	AC	2 ms 6,944 KB
testcase_47	AC	2 ms 6,940 KB
testcase_48	AC	2 ms 6,944 KB
testcase_49	AC	2 ms 6,944 KB
testcase_50	AC	2 ms 6,944 KB
testcase_51	AC	1 ms 6,944 KB
testcase_52	AC	2 ms 6,944 KB
testcase_53	AC	2 ms 6,944 KB
testcase_54	AC	2 ms 6,940 KB
testcase_55	AC	2 ms 6,940 KB
testcase_56	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin())
#define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin())

using ll=long long int;
using ull=unsigned long long;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);}
template<typename T>int popcnt(T x){return __builtin_popcountll(x);}
template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));}
template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));}
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>

class FastIO{
    static constexpr int L=1<<16;
    char rdbuf[L];
    int rdLeft=0,rdRight=0;
    inline void reload(){
        int len=rdRight-rdLeft;
        memmove(rdbuf,rdbuf+rdLeft,len);
        rdLeft=0,rdRight=len;
        rdRight+=fread(rdbuf+len,1,L-len,stdin);
    }
    inline bool skip(){
        for(;;){
            while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;
            if(rdLeft==rdRight){
                reload();
                if(rdLeft==rdRight)return false;
            }
            else break;
        }
        return true;
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__int128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__uint128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        return true;
    }
    template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        if(rdbuf[rdLeft]!='.')return true;
        rdLeft++;
        T base=.1;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x+=base*(rdbuf[rdLeft++]^48);
            base*=.1;
        }
        if(neg)x=-x;
        return true;
    }
    inline bool _read(char& x){
        if(!skip())return false;
        if(rdLeft+1>=rdRight)reload();
        x=rdbuf[rdLeft++];
        return true;
    }
    inline bool _read(string& x){
        if(!skip())return false;
        for(;;){
            int pos=rdLeft;
            while(pos<rdRight and rdbuf[pos]>' ')pos++;
            x.append(rdbuf+rdLeft,pos-rdLeft);
            if(rdLeft==pos)break;
            rdLeft=pos;
            if(rdLeft==rdRight)reload();
            else break;
        }
        return true;
    }
    template<typename T>inline bool _read(vector<T>& v){
        for(auto& x:v){
            if(!_read(x))return false;
        }
        return true;
    }

    char wtbuf[L],tmp[50];
    int wtRight=0;
    inline void _write(const char& x){
        if(wtRight>L-32)flush();
        wtbuf[wtRight++]=x;
    }
    inline void _write(const string& x){
        for(auto& c:x)_write(c);
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){
        if(wtRight>L-32)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {
                switch (sizeof(x)) {
                case 2: _write("32768"); return;
                case 4: _write("2147483648"); return;
                case 8: _write("9223372036854775808"); return;
                }
            }
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__int128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__uint128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(double x){
        ostringstream oss;
        oss << fixed << setprecision(15) << double(x);
        string s = oss.str();
        _write(s);
    }
    template<typename T>inline void _write(const vector<T>& v){
        rep(i,0,v.size()){
            if(i)_write(' ');
            _write(v[i]);
        }
    }
public:
    FastIO(){}
    ~FastIO(){flush();}
    inline void read(){}
    template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){
        assert(_read(head));
        read(tail...); 
    }
    template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}
    template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){
        _write(head);
        write<ln,true>(tail...); 
        if(space)_write(' ');
    }
    inline void flush(){
        fwrite(wtbuf,1,wtRight,stdout);
        wtRight=0;
    }
};

/**
 * @brief Fast IO
 */
#line 3 "sol.cpp"

#line 2 "library/Graph/maxflow.hpp"

struct MaxFlow {
    struct Edge {
        int to, rev;
        ll cap;
    };
    int V;
    vector<vector<Edge>> G;
    vector<int> itr, level;
    using P = pair<int, int>;
    vector<P> es;

  public:
    MaxFlow() {}
    MaxFlow(int V) : V(V) { G.assign(V, vector<Edge>()); }
    int add_vertex() {
        G.push_back(vector<Edge>());
        return V++;
    }
    void add_edge(int from, int to, ll cap) {
        es.push_back({from, (int)G[from].size()});
        G[from].push_back({to, (int)G[to].size(), cap});
        G[to].push_back({from, (int)G[from].size() - 1, 0});
    }
    struct Type {
        int from, to;
        ll cap, recap;
    };
    Type get_edge(int i) {
        auto [from, pos] = es[i];
        auto e = G[from][pos];
        auto re = G[e.to][e.rev];
        return Type{from, e.to, e.cap, re.cap};
    }
    void bfs(int s) {
        level.assign(V, -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto &e : G[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
    }
    ll dfs(int v, int t, ll f) {
        if (v == t)
            return f;
        for (int &i = itr[v]; i < (int)G[v].size(); i++) {
            Edge &e = G[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                ll d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d, G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    ll run(int s, int t) {
        ll ret = 0, f;
        while (bfs(s), level[t] >= 0) {
            itr.assign(V, 0);
            while ((f = dfs(s, t, INF)) > 0)
                ret += f;
        }
        return ret;
    }
};

/**
 * @brief Maximum Flow
 */
#line 5 "sol.cpp"

// yosupo orz
template <class Cap, class Cost> struct MinCostFlow {
    struct X {
        int from, to;
        Cap lb, ub, flow;
        Cost cost;
    };
    struct Edge {
        int to, rev;
        Cap cap;
        Cost cost;
    };
    using P = pair<int, int>;
    int n, m;
    vector<X> es;
    vector<Cap> exc;
    vector<Cost> dual;
    vector<vector<Edge>> g;
    Cost MX;
    MinCostFlow(int _n) : n(_n), m(0), exc(n), dual(n), g(n), MX(0) {}
    void add_edge(int from, int to, Cap lb, Cap ub, Cost cost) {
        m++;
        chmax(MX, cost);
        chmax(MX, -cost);
        es.push_back({from, to, lb, ub, 0, cost});
    }
    void add_excess(int v, Cap c) { exc[v] += c; }
    pair<bool, Cost> run() {
        MaxFlow mf(n + 2);
        int S = n, T = n + 1;
        Cap psum = 0, nsum = 0;
        rep(i, 0, n) {
            if (exc[i] > 0) {
                psum += exc[i];
                mf.add_edge(S, i, exc[i]);
            }
            if (exc[i] < 0) {
                nsum += -exc[i];
                mf.add_edge(i, T, -exc[i]);
            }
        }
        for (auto &e : es) {
            exc[e.to] += e.lb;
            exc[e.from] -= e.lb;
            mf.add_edge(e.from, e.to, e.ub - e.lb);
        }

        if (psum != nsum or mf.run(S, T) != psum)
            return {false, 0};

        using P = pair<int, int>;
        vector<P> pos;
        rep(i, 0, m) {
            auto e = mf.get_edge(i);
            Cost cost = es[i].cost * n;
            int fid = SZ(g[e.from]), tid = SZ(g[e.to]);
            if (e.from == e.to)
                tid++;
            pos.push_back({e.from, fid});
            g[e.from].push_back({e.to, tid, e.cap, cost});
            g[e.to].push_back({e.from, fid, e.recap, -cost});
        }

        // solve
        Cost eps = MX * n + 1;
        while (eps > 1) {
            eps = max<Cost>(eps >> 2, 1);
            refine(eps);
        }

        Cost ret = 0;
        rep(i, 0, m) {
            auto [from, fid] = pos[i];
            es[i].flow = es[i].ub - g[from][fid].cap;
            ret += es[i].flow * es[i].cost;
        }
        for (;;) {
            bool upd = 0;
            rep(i, 0, n) {
                for (auto &e : g[i])
                    if (e.cap) {
                        auto cost = dual[i] + e.cost / n;
                        if (chmin(dual[e.to], cost)) {
                            upd = 1;
                        }
                    }
            }
            if (!upd)
                break;
        }
        return {true, ret};
    }

  private:
    void refine(Cost &eps) {
        vector<bool> used(n);
        queue<int> que;
        vector<int> iter(n);

        auto cost = [&](int from, const Edge &e) {
            return e.cost + dual[from] - dual[e.to];
        };
        auto push = [&](int from, Edge &e, Cap cap) {
            exc[from] -= cap;
            exc[e.to] += cap;
            g[e.to][e.rev].cap += cap;
            e.cap -= cap;
        };
        auto relabel = [&](int v) {
            iter[v] = 0;
            Cost down = MX * (n + 1);
            for (auto &e : g[v])
                if (e.cap) {
                    chmin(down, eps + cost(v, e));
                }
            dual[v] -= down;
            que.push(v);
            used[v] = 1;
        };

        rep(i, 0, n) {
            for (auto &e : g[i])
                if (e.cap and cost(i, e) < 0) {
                    push(i, e, e.cap);
                }
        }
        rep(i, 0, n) if (exc[i] > 0) {
            used[i] = 1;
            que.push(i);
        }
        while (!que.empty()) {
            auto v = que.front();
            que.pop();
            used[v] = 0;
            for (int &i = iter[v]; i < SZ(g[v]); i++) {
                auto &e = g[v][i];
                if (e.cap and cost(v, e) < 0) {
                    push(v, e, min(exc[v], e.cap));
                    if (!used[e.to] and exc[e.to] > 0) {
                        used[e.to] = 1;
                        que.push(e.to);
                    }
                    if (exc[v] == 0)
                        break;
                }
            }
            if (exc[v] > 0)
                relabel(v);
        }
        eps = 0;
        rep(i, 0, n) {
            for (auto &e : g[i])
                if (e.cap) {
                    chmax(eps, -cost(i, e));
                }
        }
    }
};

FastIO io;
int main() {
    int n, m, k, L;
    io.read(n, m, k, L);
    vector<int> x(L), y(L), z(L);
    rep(i, 0, L) { io.read(x[i], y[i], z[i]); }

    MinCostFlow<ll, ll> buf(n + m + 1);
    int S = n + m;
    rep(i, 0, n) { buf.add_edge(S, i, 0, 1, 0); }
    rep(i, 0, m) { buf.add_edge(n + i, S, 0, 1, 0); }
    rep(i, 0, L) { buf.add_edge(x[i] - 1, y[i] - 1 + n, 0, 1, -(1 << z[i])); }
    auto [_, ret] = buf.run();
    io.write(-ret);
    return 0;
}

yukicoder

結果

テストケース

ソースコード