結果

問題 No.2478 Disjoint-Sparse-Table Optimization
ユーザー 👑 rin204rin204
提出日時 2023-09-03 20:56:52
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 8,415 bytes
コンパイル時間 4,948 ms
コンパイル使用メモリ 282,480 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-13 01:38:51
合計ジャッジ時間 5,131 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#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;
    vector<int> L(Q), R(Q);
    for (int i = 0; i < Q; i++) cin >> L[i] >> R[i];
    vector<ll> A(2 * Q);
    for (int i = 0; i < 2 * Q; i++) cin >> A[i];
    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] - 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] - cum[l2 - 1]);
            }
        }
    }
    ans -= G.run().second;
    cout << ans << endl;
}
0