// Bogdan Ciobanu
// Min-cut solutions
#include "homecoming.h"
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int kMaxN = 2.5e6;
const int kNil = -1;
const int64 kInf = numeric_limits<int64>::max() / 2;
class MaxFlowSolver {
public:
MaxFlowSolver(int n)
: head_(n, kNil) {}
virtual ~MaxFlowSolver() = default;
void AddEdge(int from, int to, int64 cap) {
edges_.emplace_back(to, cap, head_[from]);
head_[from] = static_cast<int>(edges_.size()) - 1;
edges_.emplace_back(from, 0, head_[to]);
head_[to] = static_cast<int>(edges_.size() - 1);
}
virtual int64 Compute(int, int) = 0;
protected:
struct Edge {
int to; int64 cap; int next;
Edge(int to_=0, int64 cap_=0, int next_=-1)
: to(to_),
cap(cap_),
next(next_) {}
};
vector<Edge> edges_;
vector<int> head_;
};
class FordFulkersonMethod : public MaxFlowSolver {
public:
FordFulkersonMethod(int n)
: MaxFlowSolver(n),
dist_(n) {}
int64 Compute(int s, int d) override {
int64 result = 0;
while (FindPath(s, d)) {
result += PushFlow(s, d);
}
return result;
}
virtual int64 PushFlow(const int, const int) = 0;
protected:
vector<int> dist_;
private:
bool FindPath(const int source, const int destination) {
queue<int> bfq;
fill(dist_.begin(), dist_.end(), kNil);
dist_[source] = 0;
bfq.push(source);
while (not bfq.empty()) {
const int node = bfq.front(); bfq.pop();
for (int i = head_[node]; i != kNil; i = edges_[i].next) {
const Edge& e = edges_[i];
if (dist_[e.to] == kNil and e.cap > 0) {
dist_[e.to] = dist_[node] + 1;
bfq.push(e.to);
}
}
}
return dist_[destination] != kNil;
}
};
class Dinic : public FordFulkersonMethod {
public:
Dinic(int n)
: FordFulkersonMethod(n),
at_(n) {}
int64 PushFlow(int s, int d) override {
int64 result = 0;
at_ = head_;
while (int64 pushed = Push(s, d, kInf)) {
result += pushed;
}
return result;
}
private:
int64 Push(int node, const int destination, int64 flow) {
if (flow == 0 or node == destination) {
return flow;
}
for (int& i = at_[node]; i != kNil; i = edges_[i].next) {
const Edge& e = edges_[i];
if (dist_[e.to] == dist_[node] + 1) {
int64 pushed = Push(e.to, destination, min(flow, e.cap));
if (pushed != 0) {
edges_[i ^ 0].cap -= pushed;
edges_[i ^ 1].cap += pushed;
return pushed;
}
}
}
return 0;
}
vector<int> at_;
};
class EdmondsKarp : public FordFulkersonMethod {
public:
EdmondsKarp(int n)
: FordFulkersonMethod(n) {}
int64 PushFlow(int s, int d) override {
vector<int> path;
int64 flow = kInf;
while (d != s) {
for (int i = head_[d]; i != kNil; i = edges_[i].next) {
if (dist_[edges_[i].to] == dist_[d] - 1 and edges_[i ^ 1].cap > 0) {
flow = min(flow, edges_[i ^ 1].cap);
path.push_back(i ^ 1);
d = edges_[i].to;
break;
}
}
}
for (auto e : path) {
edges_[e ^ 0].cap -= flow;
edges_[e ^ 1].cap += flow;
}
return flow;
}
};
class PushRelabel : public MaxFlowSolver {
public:
PushRelabel(int n)
: MaxFlowSolver(n),
excess_(n),
dist_(n),
cnt_(n + 1),
active_(n),
layer_(n),
n_(n) {}
int64 Compute(int s, int d) override {
for (int i = head_[s]; i != kNil; i = edges_[i].next) {
const Edge& e = edges_[i];
excess_[s] += e.cap;
}
cnt_[0] = static_cast<int>(excess_.size());
Enqueue(s);
active_[d] = true;
w = 0;
while (w >= 0) {
if (layer_[w].empty()) {
--w;
continue;
}
int u = layer_[w].back();
active_[u] = false;
layer_[w].pop_back();
Discharge(u);
}
return excess_[d];
}
private:
void Enqueue(int node) {
if (not active_[node] and excess_[node] > 0 and dist_[node] < n_) {
active_[node] = true;
layer_[dist_[node]].push_back(node);
if (dist_[node] > w) {
w = dist_[node];
}
}
}
void Discharge(int node) {
for (int i = head_[node]; i != kNil; i = edges_[i].next) {
const Edge& e = edges_[i];
if (excess_[node] > 0) {
int64 push = min(excess_[node], edges_[i].cap);
if (dist_[e.to] + 1 == dist_[node]) {
edges_[i ^ 0].cap -= push;
edges_[i ^ 1].cap += push;
excess_[e.to] += push;
excess_[node] -= push;
Enqueue(e.to);
}
} else {
break;
}
}
if (excess_[node] > 0) {
if (cnt_[dist_[node]] == 1) {
for (int i = 0; i < n_; ++i) {
if (dist_[i] >= dist_[node]) {
--cnt_[dist_[i]];
if (dist_[i] < n_) {
dist_[i] = n_;
}
++cnt_[dist_[i]];
Enqueue(i);
}
}
} else {
--cnt_[dist_[node]];
dist_[node] = n_;
for (int i = head_[node]; i != kNil; i = edges_[i].next) {
const Edge& e = edges_[i];
if (e.cap > 0 and dist_[node] > dist_[e.to] + 1) {
dist_[node] = dist_[e.to] + 1;
}
}
++cnt_[dist_[node]];
Enqueue(node);
}
}
}
vector<int64> excess_;
vector<int> dist_, cnt_;
vector<bool> active_;
vector<vector<int>> layer_;
const int n_;
int w;
};
enum kNetworkType {
kSimple,
kSegmentTree,
kSparseTable,
kOptimal
};
template <typename solver_t, kNetworkType type>
int64 solve(int n, int k, int a[], int b[]) {
static_assert(is_base_of<MaxFlowSolver, solver_t>::value);
solver_t* solver;
if (type == kSimple) {
solver = new solver_t(2 * (n + 1));
for (int i = 0; i < n; ++i) {
solver->AddEdge(0, i + 2, a[i]);
solver->AddEdge(n + i + 2, 1, b[i]);
for (int j = 0; j < k; ++j) {
solver->AddEdge(i + 2, (i + j) % n + 2 + n, kInf);
}
}
} else if (type == kSegmentTree) {
solver = new solver_t(3 * n + 2);
function<void(int, int, int)> AddRangeEdges = [&](int from, int lhs, int rhs) {
for (lhs += n, rhs += n + 1; lhs < rhs; lhs >>= 1, rhs >>= 1) {
if (lhs & 1) {
solver->AddEdge(from, n + 2 + lhs, kInf);
++lhs;
}
if (rhs & 1) {
--rhs;
solver->AddEdge(from, n + 2 + rhs, kInf);
}
}
};
// build segment tree structure
for (int i = n - 1; i > 0; --i) {
solver->AddEdge(n + 2 + i, n + 2 + 2 * i + 0, kInf);
solver->AddEdge(n + 2 + i, n + 2 + 2 * i + 1, kInf);
}
// build network
for (int i = 0; i < n; ++i) {
solver->AddEdge(0, 2 + i, a[i]);
solver->AddEdge(n + 2 + n + i, 1, b[i]);
if (i + k - 1 >= n) {
AddRangeEdges(2 + i, i, n - 1);
AddRangeEdges(2 + i, 0, (i + k - 1) % n);
} else {
AddRangeEdges(2 + i, i, i + k - 1);
}
}
} else if (type == kSparseTable) {
vector<vector<int>> table;
int id = 2 + n;
for (int i = 0; (1 << i) <= n; ++i) {
vector<int> num;
for (int j = 0; j + (1 << i) - 1 < n; ++j) {
num.push_back(id++);
}
table.push_back(num);
}
solver = new solver_t(id + 1);
function<void(int, int, int)> AddRangeEdges = [&](int from, int lhs, int rhs) {
const int log_length = 31 - __builtin_clz(rhs - lhs + 1);
solver->AddEdge(from, table[log_length][lhs], kInf);
solver->AddEdge(from, table[log_length][rhs - (1 << log_length) + 1], kInf);
};
for (int i = 1; (1 << i) <= n; ++i) {
for (int j = 0; j + (1 << i) - 1 < n; ++j) {
solver->AddEdge(table[i][j], table[i - 1][j], kInf);
solver->AddEdge(table[i][j], table[i - 1][j + (1 << (i - 1))], kInf);
}
}
for (int i = 0; i < n; ++i) {
solver->AddEdge(0, 2 + i, a[i]);
solver->AddEdge(table[0][i], 1, b[i]);
if (i + k - 1 >= n) {
AddRangeEdges(2 + i, i, n - 1);
AddRangeEdges(2 + i, 0, (i + k - 1) % n);
} else {
AddRangeEdges(2 + i, i, i + k - 1);
}
}
} else {
solver = new solver_t(4 * n + 2);
for (int i = 0; i < n; ++i) {
if (i % k != 0) {
solver->AddEdge(2 * n + 2 + i - 1, 2 * n + 2 + i, kInf);
solver->AddEdge(3 * n + 2 + i, 3 * n + 2 + i - 1, kInf);
}
solver->AddEdge(2 * n + 2 + i, n + 2 + i, kInf);
solver->AddEdge(3 * n + 2 + i, n + 2 + i, kInf);
}
for (int i = 0; i < n; ++i) {
solver->AddEdge(0, 2 + i, a[i]);
solver->AddEdge(n + 2 + i, 1, b[i]);
if (i + k - 1 >= n) {
solver->AddEdge(2 + i, 2 * n + 2 + i, kInf);
if (i / k != (n - 1) / k) {
solver->AddEdge(2 + i, 2 * n + 2 + (n - 1) / k * k, kInf);
}
solver->AddEdge(2 + i, 3 * n + 2 + (i + k - 1) % n, kInf);
} else {
solver->AddEdge(2 + i, 2 * n + 2 + i, kInf);
if (i % k != 0) {
solver->AddEdge(2 + i, 3 * n + 2 + i + k - 1, kInf);
}
}
}
}
int64 result = 0;
for (int i = 0; i < n; ++i) {
result += a[i];
}
result -= solver->Compute(0, 1);
delete solver;
return result;
}
int64 solve(int n, int k, int a[], int b[]) {
return solve<PushRelabel, kOptimal>(n, k, a, b);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
16 ms |
1060 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1060 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1060 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
16 ms |
1060 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1060 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1060 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1060 KB |
Output is correct |
| 6 |
Correct |
868 ms |
4552 KB |
Output is correct |
| 7 |
Execution timed out |
1068 ms |
4560 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1043 ms |
263168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
16 ms |
1060 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1060 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1060 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1060 KB |
Output is correct |
| 6 |
Correct |
868 ms |
4552 KB |
Output is correct |
| 7 |
Execution timed out |
1068 ms |
4560 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
