Submission #1230647

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

colouring

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

const int MAXV = 8005;     // Máximo de vértices (2000 + 2000 diagonais * 2)
const int MAXE = 20000005; // Máximo de arestas (até 2 milhões células * 2)
const long long INF = 1e18;

struct Edge {
    int to, next;
    long long cap;
} edge[MAXE];

int head[MAXV], cur[MAXV], level[MAXV];
int tot = 0;

void init(int V) {
    tot = 0;
    fill(head, head + V, -1);
}

void add_edge(int u, int v, long long cap) {
    edge[tot] = {v, head[u], cap};
    head[u] = tot++;
    edge[tot] = {u, head[v], 0};
    head[v] = tot++;
}

bool bfs(int s, int t) {
    fill(level, level + MAXV, -1);
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if (edge[i].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t] != -1;
}

long long dfs(int u, int t, long long flow) {
    if (u == t) return flow;
    for (int &i = cur[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (edge[i].cap > 0 && level[v] == level[u] + 1) {
            long long d = dfs(v, t, min(flow, edge[i].cap));
            if (d > 0) {
                edge[i].cap -= d;
                edge[i ^ 1].cap += d;
                return d;
            }
        }
    }
    return 0;
}

long long max_flow(int s, int t) {
    long long flow = 0;
    while (bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        long long f;
        while ((f = dfs(s, t, INF)) > 0)
            flow += f;
    }
    return flow;
}

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

    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];

    int S = 0, T = 1;
    int base_c1 = 2;
    int base_c2 = base_c1 + len;

    int V = base_c2 + len; // número total de vértices

    init(V);

    // Conecta source -> diagonais c1
    for (int i = 0; i < len; ++i)
        add_edge(S, base_c1 + i, c1[i]);

    // Conecta diagonais c2 -> sink
    for (int i = 0; i < len; ++i)
        add_edge(base_c2 + i, T, c2[i]);

    // Conecta c1 -> c2 para cada célula (i,j)
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int id1 = i - j + n - 1; // índice de c1
            int id2 = i + j;         // índice de c2
            add_edge(base_c1 + id1, base_c2 + id2, INF);
        }
    }

    cout << max_flow(S, T) << "\n";
    return 0;
}

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