#911333 (C++23) No.2478 Disjoint-Sparse-Table Optimization

• 問題: No.2478 Disjoint-Sparse-Table Optimization
• ユーザー: 👑 rin204
• 提出日時: 2023-09-06 23:21:31
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 6 ms / 2,000 ms
• コード長: 8,734 bytes
• コンパイル時間: 4,826 ms
• コンパイル使用メモリ: 286,996 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-24 17:33:59
• 合計ジャッジ時間: 5,346 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	4 ms; 5,376 KB
testcase_04	AC	5 ms; 5,376 KB
testcase_05	AC	3 ms; 5,376 KB
testcase_06	AC	3 ms; 5,376 KB
testcase_07	AC	5 ms; 5,376 KB
testcase_08	AC	4 ms; 5,376 KB
testcase_09	AC	4 ms; 5,376 KB
testcase_10	AC	5 ms; 5,376 KB
testcase_11	AC	5 ms; 5,376 KB
testcase_12	AC	3 ms; 5,376 KB
testcase_13	AC	6 ms; 5,376 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;

//// https://tko919.github.io/library/Graph/generalweightedmatching.hpp
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define ALL(v) (v).begin(), (v).end()

using ll     = long long int;
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;
}

// reference: http://www.cs.kent.edu/~dragan/GraphAn/p23-galil.pdf
class GeneralWeightedMatching {
    struct E {
        int u, v;
        ll w;
    };
    int n, m, in;
    vector<vector<E>> G;
    vector<int> mate, slack, root, par, isS, used;
    vector<vector<int>> flower, belong;
    vector<ll> dual;
    queue<int> que;

    ll dist(const E &e) {
        return dual[e.u] + dual[e.v] - e.w;
    }
    void update(int u, int v) {
        if (!slack[v] or dist(G[u][v]) < dist(G[slack[v]][v])) slack[v] = u;
    }
    void recalc(int v) {
        slack[v] = 0;
        rep(i, 1, n + 1) if (G[i][v].w and root[i] != v and isS[root[i]] == 1) update(i, v);
    }
    void push(int v) {
        if (v <= n)
            que.push(v);
        else
            for (auto &nxt : flower[v]) push(nxt);
    }
    void set(int v, int rt) {
        root[v] = rt;
        if (v > n)
            for (auto &nxt : flower[v]) set(nxt, rt);
    }
    int findeven(int b, int v) {
        int pos = find(ALL(flower[b]), v) - flower[b].begin();
        if (pos & 1) {
            reverse(flower[b].begin() + 1, flower[b].end());
            pos = flower[b].size() - pos;
        }
        return pos;
    }
    void match(int u, int v) {
        mate[u] = G[u][v].v;
        if (u > n) {
            int x   = belong[u][G[u][v].u];
            int pos = findeven(u, x);
            rep(i, 0, pos) match(flower[u][i], flower[u][i ^ 1]);
            match(x, v);
            rotate(flower[u].begin(), flower[u].begin() + pos, flower[u].end());
        }
    }
    void link(int u, int v) {
        for (;;) {
            int nv = root[mate[u]];
            match(u, v);
            if (!nv) break;
            v = nv, u = root[par[nv]];
            match(v, u);
        }
    }
    void make(int u, int v, int lca) {
        int id = n + 1;
        while (id <= m and root[id]) id++;
        if (id > m) m++;
        flower[id].clear();
        rep(i, 1, m + 1) G[id][i].w = G[i][id].w = 0;
        rep(i, 1, n + 1) belong[id][i]           = 0;
        isS[id] = 1, dual[id] = 0, mate[id] = mate[lca];
        while (u != lca) {
            flower[id].push_back(u);
            u = root[mate[u]];
            push(u);
            flower[id].push_back(u);
            u = root[par[u]];
        }
        flower[id].push_back(lca);
        reverse(ALL(flower[id]));
        while (v != lca) {
            flower[id].push_back(v);
            v = root[mate[v]];
            push(v);
            flower[id].push_back(v);
            v = root[par[v]];
        }
        set(id, id);
        for (auto &c : flower[id]) {
            rep(i, 1, m + 1) if (!G[id][i].w or dist(G[c][i]) < dist(G[id][i])) {
                G[id][i] = G[c][i], G[i][id] = G[i][c];
            }
            rep(i, 1, n + 1) if (belong[c][i]) belong[id][i] = c;
        }
        recalc(id);
    }
    void expand(int b) {
        for (auto &c : flower[b]) set(c, c);
        int x  = belong[b][G[b][par[b]].u];
        isS[x] = 2, par[x] = par[b];
        int pos = findeven(b, x);
        for (int i = 0; i < pos; i += 2) {
            int T = flower[b][i], S = flower[b][i + 1];
            isS[S] = 1, isS[T] = 2;
            par[T]   = G[S][T].u;
            slack[S] = slack[T] = 0;
            push(S);
        }
        rep(i, pos + 1, flower[b].size()) {
            isS[flower[b][i]] = 0;
            recalc(flower[b][i]);
        }
        flower[b].clear();
        root[b] = 0;
    }
    bool path(const E &e) {
        int u = root[e.u], v = root[e.v];
        if (!isS[v]) {
            par[v]   = e.u;
            isS[v]   = 2;
            int nu   = root[mate[v]];
            slack[v] = slack[nu] = 0;
            isS[nu]              = 1;
            push(nu);
        } else if (isS[v] == 1) {
            int lca = 0, bu = u, bv = v;
            in++;
            while (bu) {
                used[bu] = in;
                bu       = root[mate[bu]];
                if (bu) bu = root[par[bu]];
            }
            while (bv) {
                if (used[bv] == in) {
                    lca = bv;
                    break;
                }
                bv = root[mate[bv]];
                if (bv) bv = root[par[bv]];
            }
            if (lca)
                make(u, v, lca);
            else {
                link(u, v), link(v, u);
                return true;
            }
        }
        return false;
    }
    bool augment() {
        isS = slack = par = vector<int>(n * 2);
        que               = queue<int>();
        rep(i, 1, m + 1) if (root[i] == i and !mate[i]) {
            isS[i] = 1;
            push(i);
        }
        if (que.empty()) return false;
        for (;;) {
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                rep(i, 1, n + 1) if (G[v][i].w and root[i] != root[v]) {
                    if (!dist(G[v][i])) {
                        if (path(G[v][i])) return true;
                    } else if (isS[root[i]] != 2)
                        update(v, root[i]);
                }
            }
            ll delta = INF;
            rep(i, n + 1, m + 1) if (root[i] == i and isS[i] == 2) chmin(delta, dual[i] / 2);
            rep(i, 1, m + 1) if (root[i] == i and slack[i] and isS[i] != 2) {
                if (!isS[i])
                    chmin(delta, dist(G[slack[i]][i]));
                else
                    chmin(delta, dist(G[slack[i]][i]) / 2);
            }
            rep(i, 1, n + 1) {
                if (isS[root[i]] == 1) {
                    dual[i] -= delta;
                    if (dual[i] <= 0) return false;
                } else if (isS[root[i]] == 2)
                    dual[i] += delta;
            }
            rep(i, n + 1, m + 1) if (root[i] == i and isS[i]) {
                if (isS[i] == 1)
                    dual[i] += delta * 2;
                else
                    dual[i] -= delta * 2;
            }
            rep(i, 1, m + 1) if (root[i] == i and slack[i] and root[slack[i]] != i) {
                if (dist(G[slack[i]][i]) == 0 and path(G[slack[i]][i])) return true;
            }
            rep(i, n + 1, m + 1) if (root[i] == i and isS[i] == 2 and dual[i] == 0) expand(i);
        }
    }

  public:
    GeneralWeightedMatching(int _n) : n(_n), m(n), in(0), G(n * 2, vector<E>(n * 2)), mate(n * 2), root(n * 2), used(n * 2), flower(n * 2), belong(n * 2, vector<int>(n * 2)), dual(n * 2) {
        rep(i, 0, n + 1) {
            root[i]      = i;
            belong[i][i] = i;
            if (i) dual[i] = INF;
            rep(j, 0, n + 1) G[i][j] = E{i, j, 0};
        }
    }
    void add_edge(int u, int v, ll w) {
        u++, v++;
        chmax(G[u][v].w, w * 2);
        chmax(G[v][u].w, w * 2);
    }
    pair<vector<int>, ll> run() {
        while (augment())
            ;
        vector<int> res(n, -1);
        ll weight = 0;
        rep(i, 1, n + 1) {
            if (mate[i]) {
                res[i - 1] = mate[i] - 1;
                if (i < mate[i]) weight += G[i][mate[i]].w / 2;
            }
        }
        return make_pair(res, weight);
    }
};

int main() {
    int Q;
    cin >> Q;
    assert(1 <= Q && Q <= 100);
    vector<int> L(Q), R(Q);
    set<int> se;
    for (int i = 0; i < Q; i++) {
        cin >> L[i] >> R[i];

        assert(1 <= L[i] && L[i] <= R[i] && R[i] <= 2 * Q);
        assert(!se.count(L[i]));
        assert(!se.count(R[i]));
        se.insert(L[i]);
        se.insert(R[i]);
    }
    vector<ll> A(2 * Q);
    for (int i = 0; i < 2 * Q - 1; i++) {
        cin >> A[i];
        assert(1 <= A[i] && A[i] <= 1000000000);
    }
    vector<ll> cum(2 * Q + 1);
    cum[0] = 0;
    for (int i = 0; i < 2 * Q; i++) cum[i + 1] = cum[i] + A[i];

    GeneralWeightedMatching G(Q);
    ll ans = 0;
    for (int i = 0; i < Q; i++) {
        int l1 = L[i];
        int r1 = R[i];
        ans += cum[r1 - 1] - cum[l1 - 1];
        for (int j = 0; j < Q; j++) {
            int l2 = L[j];
            int r2 = R[j];
            if (l1 < l2 && l2 < r1 && r1 < r2) {
                G.add_edge(i, j, cum[r1 - 1] - cum[l2 - 1]);
            }
        }
    }
    ans -= G.run().second;
    cout << ans << endl;
}