結果
| 問題 | No.2478 Disjoint-Sparse-Table Optimization |
| ユーザー |
👑  rin204
|
| 提出日時 | 2023-09-03 20:56:52 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 8,415 bytes |
| コンパイル時間 | 4,876 ms |
| コンパイル使用メモリ | 281,032 KB |
| 実行使用メモリ | 4,484 KB |
| 最終ジャッジ日時 | 2023-09-03 20:57:00 |
| 合計ジャッジ時間 | 5,539 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,380 KB |
| testcase_01 | AC | 2 ms
4,380 KB |
| testcase_02 | AC | 2 ms
4,376 KB |
| testcase_03 | AC | 3 ms
4,380 KB |
| testcase_04 | AC | 3 ms
4,384 KB |
| testcase_05 | AC | 4 ms
4,384 KB |
| testcase_06 | AC | 3 ms
4,376 KB |
| testcase_07 | AC | 4 ms
4,380 KB |
| testcase_08 | AC | 4 ms
4,380 KB |
| testcase_09 | AC | 4 ms
4,376 KB |
| testcase_10 | AC | 5 ms
4,380 KB |
| testcase_11 | AC | 4 ms
4,380 KB |
| testcase_12 | AC | 3 ms
4,484 KB |
| testcase_13 | AC | 5 ms
4,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;
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;
}