제출 #59726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59726		model_code	Homecoming (BOI18_homecoming)	C++17	13 / 100	1068 ms	263168 KiB

homecoming

// 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);
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38