結果
問題 | No.2478 Disjoint-Sparse-Table Optimization |
ユーザー |
👑 |
提出日時 | 2023-09-06 23:21:31 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 12 |
ソースコード
#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.pdfclass 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);elsefor (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]));elsechmin(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;elsedual[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;}