Submission #1350474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350474		Faisal_Saqib	Domino (COCI15_domino)	C++20	0 / 160	160 ms	188208 KiB

domino

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

typedef long long ll;

struct Edge {
    int to, rev, cap;
    ll cost;
};

struct MCMF {
    int N;
    vector<vector<Edge>> g;

    vector<ll> dist;
    vector<int> inq, par_v, par_e;

    MCMF(int n) : N(n), g(n), dist(n), inq(n), par_v(n), par_e(n) {}

    void addEdge(int s, int t, int cap, ll cost) {
        g[s].push_back({t, (int)g[t].size(), cap, cost});
        g[t].push_back({s, (int)g[s].size() - 1, 0, -cost});
    }

    pair<int,ll> maxCostMaxFlow(int s, int t, int maxf) {
        int flow = 0;
        ll cost = 0;

        while(flow < maxf) {
            fill(dist.begin(), dist.end(), LLONG_MIN);
            fill(inq.begin(), inq.end(), 0);

            dist[s] = 0;
            queue<int> q;
            q.push(s);
            inq[s] = 1;

            // SPFA (maximize cost)
            while(!q.empty()) {
                int v = q.front(); q.pop();
                inq[v] = 0;

                for(int i = 0; i < (int)g[v].size(); i++) {
                    Edge &e = g[v][i];
                    if(e.cap > 0 && dist[e.to] < dist[v] + e.cost) {
                        dist[e.to] = dist[v] + e.cost;
                        par_v[e.to] = v;
                        par_e[e.to] = i;
                        if(!inq[e.to]) {
                            q.push(e.to);
                            inq[e.to] = 1;
                        }
                    }
                }
            }

            // stop if no useful path
            if(dist[t] <= 0) break;

            int addf = maxf - flow;

            int v = t;
            while(v != s) {
                Edge &e = g[par_v[v]][par_e[v]];
                addf = min(addf, e.cap);
                v = par_v[v];
            }

            v = t;
            while(v != s) {
                Edge &e = g[par_v[v]][par_e[v]];
                e.cap -= addf;
                g[v][e.rev].cap += addf;
                v = par_v[v];
            }

            flow += addf;
            cost += dist[t] * addf;
        }

        return {flow, cost};
    }
};

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

    int n, k;
    cin >> n >> k;

    vector<vector<int>> a(n, vector<int>(n));
    ll tot=0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> a[i][j],tot+=a[i][j];

    int V = n*n + 2;
    int S = n*n;
    int T = n*n + 1;

    MCMF mf(V);

    auto id = [&](int i, int j) {
        return i*n + j;
    };

    // ONLY 2 DIRECTIONS (optimization)
    int dx[4] = {1, 0,-1,0};
    int dy[4] = {0, 1,0,-1};

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {

            if((i + j) % 2 == 1) {
                // black → source
                mf.addEdge(S, id(i,j), 1, 0);

                for(int d = 0; d < 4; d++) {
                    int ni = i + dx[d];
                    int nj = j + dy[d];

                    if(ni >= n || nj >= n) continue;

                    // connect only once (avoid duplicates)
                    mf.addEdge(id(i,j), id(ni,nj), 1,
                               a[i][j] + a[ni][nj]);
                }
            } else {
                // white → sink
                mf.addEdge(id(i,j), T, 1, 0);
            }
        }
    }

    auto [flow, cost] = mf.maxCostMaxFlow(S, T, k);

    cout << tot-cost << "\n";

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10
• Subtask 16: 0 / 10