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

提出ソース

結果

問題	No.1615 Double Down
ユーザー	tko919
提出日時	2023-12-15 03:52:33
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	10,634 bytes
コンパイル時間	3,229 ms
コンパイル使用メモリ	225,620 KB
実行使用メモリ	24,208 KB
最終ジャッジ日時	2024-09-27 05:58:25
合計ジャッジ時間	39,060 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8,086 ms 15,192 KB
testcase_01	AC	7,932 ms 15,084 KB
testcase_02	TLE	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-

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

ソースコード

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"

struct NetworkSimplex {
    using Flow = int64_t;
    using Cost = int64_t;
    using vector_id = int32_t;
    using E_id = int32_t;
    struct Edge {
        vector_id src, dst;
        Flow flow, cap;
        Cost cost;
    };
    Cost INF = 1;
    ll delta = 0;
    int n;
    vector<Flow> B;
    vector<Cost> P;
    vector<Edge> E;
    vector<int> pei, depth;
    vector<set<int>> tree;
    NetworkSimplex(int _n) {
        n = _n;
        B.resize(n + 1);
        pei.assign(n + 1, -1);
        depth.resize(n + 1);
        P.resize(n + 1);
        tree.resize(n + 1);
    }
    int ae(vector_id a, vector_id b, Flow l, Flow u, Cost c) {
        E.push_back({a, b, 0, u - l, c});
        E.push_back({b, a, 0, 0, -c});
        delta += l * c;
        B[b] += l, B[a] -= l;
        return SZ(E) - 2;
    }
    void upd(E_id ei) {
        P[E[ei].dst] = P[E[ei].src] + E[ei].cost;
        pei[E[ei].dst] = ei ^ 1;
        depth[E[ei].dst] = 1 + depth[E[ei].src];
        dfs(E[ei].dst);
    }
    void dfs(int node) {
        for (auto &ei : tree[node])
            if (ei != pei[node])
                upd(ei);
    }
    // applies cb to a -> b and (tree path b -> a)
    template <class CB> void walk(int ei, CB cb) {
        cb(ei);
        for (vector_id a = E[ei].src, b = E[ei].dst; a != b;) {
            if (depth[a] > depth[b])
                cb(pei[a] ^ 1), a = E[pei[a]].dst;
            else
                cb(pei[b]), b = E[pei[b]].dst;
        }
    }
    ll solve() {
        const int m = SZ(E);
        for (E_id i = 0; i < m; i += 2)
            INF += abs(E[i].cost);
        rep(i, 0, n) {
            vector_id a = n, b = i;
            Cost c = B[i];
            if (c < 0)
                c *= -1, swap(a, b);
            E_id ei = ae(a, b, 0, c, -INF);
            tree[a].insert(ei), tree[b].insert(ei ^ 1);
        }
        dfs(n);
        ll answer = delta;
        E_id ptr = 0;
        const int BLOCK = n / 3 + 1;
        rep(z, 0, SZ(E) / BLOCK + 1) {
            pair<Cost, E_id> pin{0, -1};
            for (int t = 0; t < BLOCK; ++t, (++ptr) %= SZ(E)) {
                const auto &e = E[ptr];
                if (e.flow < e.cap)
                    chmin(pin, {e.cost + P[e.src] - P[e.dst], ptr});
            }
            auto [cost, ein] = pin;
            if (cost == 0)
                continue;
            pair<Cost, E_id> pout{E[ein].cap - E[ein].flow, ein};
            walk(ein, [&](E_id ei) {
                chmin(pout, {E[ei].cap - E[ei].flow, ei});
            });
            auto [flow, eout] = pout;
            walk(ein,
                 [&](E_id ei) { E[ei].flow += flow, E[ei ^ 1].flow -= flow; });
            tree[E[ein].src].insert(ein), tree[E[ein].dst].insert(ein ^ 1);
            tree[E[eout].src].erase(eout), tree[E[eout].dst].erase(eout ^ 1);
            upd(pei[E[eout].src] == eout ? ein : ein ^ 1);
            answer += ll(flow) * cost; // why can't this loop?
            z = -1;
        }
        rep(i, 0, n) {
            if (E[m + 2 * i].flow < E[m + 2 * i].cap)
                throw 5;
            answer += ll(E[m + 2 * i].flow) * INF;
        }
        return answer;
    }
};

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]); }

    NetworkSimplex buf(n + m + 1);
    int S = n + m;
    rep(i, 0, n) { buf.ae(S, i, 0, 1, 0); }
    rep(i, 0, m) { buf.ae(n + i, S, 0, 1, 0); }
    rep(i, 0, L) { buf.ae(x[i] - 1, y[i] - 1 + n, 0, 1, -(1 << z[i])); }
    ll ret = -buf.solve();
    io.write(ret);
    return 0;
}

yukicoder

結果

テストケース

ソースコード