Submission #1230645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230645		jajskao	Colouring a rectangle (eJOI19_colouring)	C++20	40 / 100	1848 ms	167936 KiB

colouring

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

struct Edge {
    int to, rev;
    long long cap;
};

class MaxFlow {
public:
    vector<vector<Edge>> adj;
    vector<int> level, iter;
    MaxFlow(int n) : adj(n), level(n), iter(n) {}

    void add_edge(int from, int to, long long cap) {
        adj[from].push_back({to, (int)adj[to].size(), cap});
        adj[to].push_back({from, (int)adj[from].size() - 1, 0});
    }

    void bfs(int s) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0; q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (auto &e : adj[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
    }

    long long dfs(int v, int t, long long f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < (int)adj[v].size(); ++i) {
            Edge &e = adj[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                long long d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    adj[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    long long max_flow(int s, int t) {
        long long flow = 0;
        while (true) {
            bfs(s);
            if (level[t] < 0) break;
            fill(iter.begin(), iter.end(), 0);
            long long f;
            while ((f = dfs(s, t, INF)) > 0)
                flow += f;
        }
        return flow;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int m, n;
    cin >> m >> n;
    int len = m + n - 1;

    vector<long long> c1(len), c2(len);
    for (int i = 0; i < len; ++i) cin >> c1[i];
    for (int i = 0; i < len; ++i) cin >> c2[i];

    // Nodes:
    // 0 - source
    // 1 to len   - c1 (diagonals of \ type)
    // len+1 to 2*len - c2 (diagonals of / type)
    // 2*len + 1 - sink
    int S = 0, T = 2 * len + 1;
    MaxFlow mf(2 * len + 2);

    for (int i = 0; i < len; ++i) {
        mf.add_edge(S, i + 1, c1[i]);
        mf.add_edge(i + 1 + len, T, c2[i]);
    }

    // Each cell (i,j) contributes an edge between c1[i - j + n - 1] and c2[i + j]
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int c1_idx = i - j + n - 1;
            int c2_idx = i + j;
            mf.add_edge(c1_idx + 1, c2_idx + len + 1, INF);
        }
    }

    cout << mf.max_flow(S, T) << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 20
• Subtask 5: 10 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20