oj.uz

Submission #1018453

# Submission time Handle Problem Language Result Execution time Memory
1018453 2024-07-10T04:49:12 Z caterpillow Domino (COCI15_domino) C++17
110 / 160
 1004 ms 524288 KB 
#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?

*/

struct Edge {
    int u, v;
    int flo, cost;
};

// max cost
struct MCMF {
    int n;
    vt<Edge> edges;  
    vt<vt<int>> adj;
    void init(int _n) {
        n = _n;
        adj.resize(n);
    }
    void ae(int u, int v, int cost) {
        int ei = size(edges);
        edges.pb({u, v, 0, cost});
        adj[u].pb(ei);
        adj[v].pb(~ei);
    }
    bool valid(int ei) {
        if (ei >= 0) return edges[ei].flo == 0;
        else return edges[~ei].flo == 1;
    }
    pi get_edge(int u, int ei) {
        if (ei >= 0) return {edges[ei].v, edges[ei].cost};
        else return {edges[~ei].u, -edges[~ei].cost};
    }
    pair<vt<int>, int> find_augmenting_path(int s, int t) {
        vt<int> par(n, -1); // parent edge
        vt<int> dist(n, inf);
        dist[s] = 0;
        vt<bool> in_queue(n);
        queue<int> q;
        q.push(s);
        while (size(q)) {
            int u = q.front(); q.pop();
            in_queue[u] = false;
            for (int ei : adj[u]) {
                if (!valid(ei)) continue;
                auto [v, cost] = get_edge(u, ei);
                if (dist[u] + cost < dist[v]) {   
                    dist[v] = dist[u] + cost;
                    par[v] = ei;
                    if (!in_queue[v]) {
                        q.push(v);
                        in_queue[v] = true;
                    }
                }
            }
        }
        vt<int> res;
        int u = t;
        while (par[u] != -1) {
            res.pb(par[u]);
            if (par[u] >= 0) u = edges[par[u]].u;
            else u = edges[~par[u]].v;
        }
        return {res, dist[t]};
    }
    int calc(int s, int t, int k) {
        int ans = 0;
        F0R (_, k) {
            auto [path, cost] = find_augmenting_path(s, t);
            ans += cost;
            for (int ei : path) {
                if (ei >= 0) edges[ei].flo = 1;
                else edges[~ei].flo = 0;
            }
        } 
        return ans;
    }
};

int n, k; 
vt<vt<int>> grid;
MCMF mcmf;

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];
        }
    }
    mcmf.init(n * n + 2);
    int s = n * n;
    int t = s + 1;
    const int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
    auto enc = [&] (int r, int c) { return r * n + c; };
    F0R (r, n) {
        F0R (c, n) {
            if ((r + c) % 2 == 0) continue;
            F0R (i, 4) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nc >= 0 && nr < n && nc < n) {
                    mcmf.ae(enc(r, c), enc(nr, nc), 0);
                }
            }
        }
    }
    F0R (r, n) {
        F0R (c, n) {
            if ((r + c) % 2 == 1) mcmf.ae(s, enc(r, c), 1000 - grid[r][c]);
            else mcmf.ae(enc(r, c), t, 1000 - grid[r][c]);
        }
    }
    int flow = mcmf.calc(s, t, k);
    int ans = 2 * k * 1000 - flow;
    cout << tot - ans << endl;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 35248 KB Output is correct
2 Correct 64 ms 35244 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 720 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 878 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 314164 KB Output is correct
2 Correct 653 ms 312236 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 139444 KB Output is correct
2 Correct 311 ms 139700 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1004 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 863 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1744 KB Output is correct
2 Correct 4 ms 1744 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 902 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 139536 KB Output is correct
2 Correct 401 ms 139708 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #16
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 907 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -