Submission #714451

#	Time	Username	Problem	Language	Result	Execution time	Memory
714451		pashka	Potatoes and fertilizers (LMIO19_bulves)	C++14	0 / 100	1067 ms	1400 KiB

bulves

#include <bits/stdc++.h>

#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

struct mincost {

    const long INF = 1e18;

    struct edge {
        int src, dst, maxCap, cost, flw, cap;
    };

    vector<edge> edges;
    vector<vector<int>> graph;

    vector<long> phi;

    void dijkstra(int s, vector<long> &d, vector<int> &prev) {
        std::fill(d.begin(), d.end(), INF);
        d[s] = 0;
        std::priority_queue<pair<long, int>> pq;
        pq.push({-d[s], s});
        while (!pq.empty()) {
            int v = pq.top().second;
            long cur_d = -pq.top().first;
            pq.pop();
            if (cur_d > d[v]) continue;
            for (int j = 0; j < graph[v].size(); ++j) {
                edge &e = edges[graph[v][j]];
                if (e.flw == e.cap) continue;
                long dd = d[v] + e.cost + phi[e.src] - phi[e.dst];
                if (dd < d[e.dst]) {
                    d[e.dst] = dd;
                    prev[e.dst] = graph[v][j];
                    pq.push({-d[e.dst], e.dst});
                }
            }
        }
    }

    void init(int n) {
        graph.resize(n);
        phi.resize(n);
    }

    void validate() {
        for (edge &e: edges) {
            if (e.flw < e.cap) {
                int x = e.src;
                int y = e.dst;
                assert (e.cost + phi[x] - phi[y] >= 0);
            }
        }
    }

    long cost = 0;

    void doubleFlow() {
        for (auto &e: edges) {
            e.cap *= 2;
            e.flw *= 2;
        }
        cost *= 2;
    }

    void incCapacity(int i) {
        auto &e = edges[i];
        auto &er = edges[i ^ 1];
        {
            if (e.cost + phi[e.src] - phi[e.dst] >= 0) {
                e.cap++;
                return;
            }
        }
        int n = graph.size();
        vector<long> dist(n);
        vector<int> prev(n);
        int s = e.dst;
        int t = e.src;
        dijkstra(s, dist, prev);
        long d2 = dist[t] - phi[s] + phi[t];
        if (d2 + e.cost < 0) {
            i = t;
            while (i != s) {
                edge &e = edges[prev[i]];
                edge &er = edges[prev[i] ^ 1];
                e.flw++;
                er.flw--;
                cost += (long) e.cost;
                i = e.src;
            }
            e.flw++;
            er.flw--;
        }
        e.cap++;
        for (int i = 0; i < n; i++) {
            if (dist[i] != INF) phi[i] += dist[i];
        }
        long dd = 0;
        for (auto &e: edges) {
            if (e.flw == e.cap) continue;
            long c = e.cost + phi[e.src] - phi[e.dst];
            dd = max(dd, -c);
        }
        for (int i = 0; i < n; i++) {
            if (dist[i] == INF) phi[i] += dd;
        }
        validate();
    }

    void minCostCirculation() {
        int n = graph.size();
        int m = edges.size() / 2;
        validate();
        for (int i = 30; i >= 0; i--) {
            doubleFlow();
            for (int j = 0; j < m; j++) {
                if (edges[2 * j].maxCap & (1 << i)) {
                    incCapacity(2 * j);
                }
            }
        }
    }

    void fordBellman() {
        int n = graph.size();
        for (int i = 0; i < n; i++) {
            phi[i] = INF;
        }
        bool ok = false;
        int c = 0;
        while (!ok) {
            c++;
            assert(c <= n);
            ok = true;
            for (edge &e: edges) {
                if (e.flw < e.cap) {
                    int x = e.src;
                    int y = e.dst;
                    if (phi[y] > phi[x] + e.cost) {
                        phi[y] = phi[x] + e.cost;
                        ok = false;
                    }
                }
            }
        }
    }

    int minCostFlow(int s, int t) {
        int n = graph.size();
        int m = edges.size();
        for (auto &e: edges) e.cap = e.maxCap;
        fordBellman();
        vector<long> dist(n);
        vector<int> prev(n);
        int fl = 0;
        while (true) {
            dijkstra(s, dist, prev);
            if (dist[t] == INF) break;
//            if (dist[t] - phi[s] + phi[t] >= 0) break;
            {
                int i = t;
                int delta = INT_MAX;
                while (i != s) {
                    edge &e = edges[prev[i]];
                    delta = std::min(delta, e.cap - e.flw);
                    i = e.src;
                }
                assert(delta >= 0);
                fl += delta;
                i = t;
                while (i != s) {
                    edge &e = edges[prev[i]];
                    edge &er = edges[prev[i] ^ 1];
                    e.flw += delta;
                    er.flw -= delta;
                    assert(e.flw <= e.cap);
                    cost += (long) e.cost * delta;
                    i = e.src;
                }
            }
            for (int i = 0; i < n; i++) {
                phi[i] += dist[i];
            }
        }
        return fl;
    }

    void addEdge(int u, int v, int cap, int cost) {
        edges.push_back({u, v, cap, cost, 0, 0});
        edges.push_back({v, u, 0, -cost, 0, 0});
        graph[u].push_back(edges.size() - 2);
        graph[v].push_back(edges.size() - 1);
    }
};


int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = x - y;
    }
    mincost mc;
    mc.init(n + 2);
    int s = n;
    int t = n + 1;
    for (int i = 0; i < n; i++) {
        if (a[i] < 0) {
            mc.addEdge(s, i, -a[i], 0);
        } else {
            mc.addEdge(i, t, a[i], 0);
        }
        if (i < n - 1) {
            mc.addEdge(i, i + 1, INT_MAX, 1);
            mc.addEdge(i + 1, i, INT_MAX, 1);
        }
    }
    mc.minCostFlow(s, t);
    cout << mc.cost << "\n";

    return 0;
}

Compilation message (stderr)

bulves.cpp: In member function 'void mincost::dijkstra(int, std::vector<long long int>&, std::vector<int>&)':
bulves.cpp:32:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for (int j = 0; j < graph[v].size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~~~~
bulves.cpp: In member function 'void mincost::minCostCirculation()':
bulves.cpp:116:13: warning: unused variable 'n' [-Wunused-variable]
  116 |         int n = graph.size();
      |             ^
bulves.cpp: In member function 'int mincost::minCostFlow(int, int)':
bulves.cpp:155:13: warning: unused variable 'm' [-Wunused-variable]
  155 |         int m = edges.size();
      |             ^

• Subtask 1: 0 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36