Submission #1018469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018469		caterpillow	Domino (COCI15_domino)	C++17	160 / 160	922 ms	80512 KiB

domino

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

max cost max flow?

*/

int n, k; 
vt<vt<int>> grid;
bool flo[2000][2000][5]; // direction index, then to source/sink

const int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
int enc(int r, int c) {
    return r * n + c;
}
pi dec(int id) {
    return {id / n, id % n};
}
bool valid(int r, int c) {
    return r >= 0 && c >= 0 && r < n && c < n;
}

// sink goes to even r + c
// you never go to the source twice
int find_augmenting_path() {
    vt<int> par(n * n, -1); // direction taken to reach here
    vt<int> dist(n * n, inf);
    vt<bool> in_queue(n * n);
    queue<pi> q;

    int ans = inf;
    pi best;

    F0R (r, n) {
        F0R (c, n) {
            if ((r + c) % 2 == 0) {
                if (!flo[r][c][4]) {
                    int id = enc(r, c);
                    in_queue[id] = true;
                    q.push({r, c});
                    dist[id] = grid[r][c];
                    par[id] = -1;
                }
            }
        }
    }

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        int id = r * n + c;
        in_queue[id] = false;
        if ((r + c) % 2 == 0) { // lhs
            F0R (i, 4) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (valid(nr, nc)) {
                    if (!flo[r][c][i]) { // no flow
                        int vid = enc(nr, nc);
                        if (dist[id] < dist[vid]) {
                            dist[vid] = dist[id];
                            par[vid] = i;
                            if (!in_queue[vid]) {
                                q.push({nr, nc});
                                in_queue[vid] = true;
                            }
                        }
                    }
                }
            }
        } else { // rhs
            F0R (i, 4) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (valid(nr, nc)) {
                    if (flo[nr][nc][(i + 2) % 4]) { // yes flow
                        int vid = enc(nr, nc);
                        if (dist[id] < dist[vid]) {
                            dist[vid] = dist[id];
                            par[vid] = i;
                            if (!in_queue[vid]) {
                                q.push({nr, nc});
                                in_queue[vid] = true;
                            }
                        }
                    }
                }
            }
            if (!flo[r][c][4]) { // check flow to sink
                if (dist[id] + grid[r][c] < ans) {
                    ans = dist[id] + grid[r][c];
                    best = {r, c};
                } 
            }
        }
    }
    auto [r, c] = best;
    flo[r][c][4] = 1;
    while (par[enc(r, c)] != -1) {
        int id = enc(r, c);
        int i = (par[id] + 2) % 4; // direction from current to prev
        int pr = r + dr[i];
        int pc = c + dc[i];
        if ((r + c) % 2 == 0) { // lhs
            flo[r][c][i] = 0; // took a backedge
        } else { // rhs
            flo[pr][pc][par[id]] = 1; // took a normal edge
        }
        r = pr;
        c = pc;
    }
    flo[r][c][4] = 1;
    return ans;
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> k;
    grid.resize(n, vt<int>(n));
    ll tot = 0;
    F0R (r, n) {
        F0R (c, n) {
            cin >> grid[r][c];
            tot += grid[r][c];
            grid[r][c] = 1000 - grid[r][c];
        }
    }
    int flow = 0;
    F0R (i, k) flow += find_augmenting_path();
    int ans = 2 * k * 1000 - flow;
    cout << tot - ans << endl;
}

Compilation message (stderr)

domino.cpp:159:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  159 | main() {
      | ^~~~

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