Submission #102014


Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int H, W;

bool check_consistency(const vector<vector<int> > &upper, const vector<int> &front, const vector<int> &side) {
    vector<vector<int> > min_at(H, vector<int>(W, 0));
    for(int r = 0; r < H; ++r) {
        for(int c = 0; c < W; ++c) {
            if(upper[r][c]) {
                min_at[r][c] = min(front[c], side[r]);
                if(min_at[r][c] == 0) return false;
            }
        }
    }
    // Check side
    for(int r = 0; r < H; ++r) {
        int max_val = 0;
        for(int c = 0; c < W; ++c) {
            if(upper[r][c]) max_val = max(max_val, min_at[r][c]);
        }
        if(max_val != side[r]) return false;
    }
    // Check front
    for(int c = 0; c < W; ++c) {
        int max_val = 0;
        for(int r = 0; r < H; ++r) {
            if(upper[r][c]) max_val = max(max_val, min_at[r][c]);
        }
        if(max_val != front[c]) return false;
    }
    return true;
}

/*
template <class Flow, class Cost>
struct edge
{
    int index;
    Flow capacity, flow;
    Cost cost;
    int back;
    edge(int i, Flow c, Cost d, int b) : index(i), capacity(c), flow(0), cost(d), back(b) {}
};

template <class Flow, class Cost>
void make_edge(vector<edge<Flow, Cost> > *g, int src, int dst, Flow c, Cost d)
{
    const int i = g[src].size(), j = g[dst].size();
    g[src].push_back(edge<Flow, Cost>(dst, c, d, j));
    g[dst].push_back(edge<Flow, Cost>(src, 0, -d, i));
}

template<class Flow, class Cost>
pair<Flow, Cost>
primal_dual(vector<edge<Flow, Cost> > *g, int N, int source, int sink, int max_flow)
{
    pair<Flow, Cost> total;
    static Cost h[MAXN], dist[MAXN];
    static pair<int,int> parent[MAXN];
    for(Flow f = max_flow; f > 0; ) {
        fill_n(dist, N, 1000000);
        dist[source] = 0;
        fill_n(parent, N, make_pair(-1, -1));

    }
}
*/

const int SIZE = 128;
const int INF = (int)1e9;
int hungarian(int N, int cost[SIZE][SIZE]) {
    vector<int> xy(N, -1), yx(N, -1), lx(N, -INF), ly(N, 0);
    for(int x = 0; x < N; ++x) {
        for(int y = 0; y < N; ++y) {
            lx[x] = max(lx[x], cost[x][y]);
        }
    }
    for(int root = 0; root < N; ++root) {
        vector<bool> left(N), right(N);
        vector<int> slack(N), slackx(N, root), prev(N, -1);
        left[root] = true;
        for(int j = 0; j < N; ++j) {
            slack[j] = lx[root] + ly[j] - cost[root][j];
        }
        while(true) {
            int d = INF;
            for(int i = 0; i < N; ++i) {
                if(!right[i]) d = min(d, slack[i]);
            }
            for(int i = 0; i < N; ++i) {
                if(left[i]) lx[i] -= d;
            }
            for(int i = 0; i < N; ++i) {
                if(right[i]) ly[i] += d;
                else slack[i] -= d;
            }

            for(int y = 0; y < N; ++y) {
                if(!right[y] && slack[y] == 0) {
                    if(yx[y] >= 0) {
                        right[y] = true;
                        int a = yx[y];
                        if(!left[a]) {
                            left[a] = true;
                            prev[a] = slackx[y];
                            for(int j = 0; j < N; ++j) {
                                if(lx[a] + ly[j] - cost[a][j] < slack[j]) {
                                    slack[j] = lx[a] + ly[j] - cost[a][j];
                                    slackx[j] = a;
                                }
                            }
                        }
                    } else {
                        for(int cx = slackx[y], cy = y, ty; cx != -1; cx = prev[cx], cy = ty) {
                            ty = xy[cx];
                            yx[cy] = cx;
                            xy[cx] = cy;
                        }
                        goto NEXT;
                    }
                }
            }
        }
NEXT:
        ;
    }
    int ret = 0;
    for(int i = 0; i < N; ++i) {
        ret += cost[i][xy[i]];
    }
    return ret;
}

int mat[SIZE][SIZE];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    cin >> H >> W;
    vector<vector<int> > upper(H, vector<int>(W, 0));
    vector<int> front(W), side(H);

    int acc = 0;
    for(int r = 0; r < H; ++r) {
        for(int c = 0; c < W; ++c) {
            cin >> upper[r][c];
            if(upper[r][c]) ++acc;
        }
    }
    for(int x = 0; x < W; ++x) {
        cin >> front[x];
        if(front[x]) acc += front[x]-1;
    }
    for(int y = 0; y < H; ++y) {
        cin >> side[y];
        if(side[y]) acc += side[y]-1;
    }

    if(!check_consistency(upper, front, side)) {
        cout << -1 << endl;
        return 0;
    }

    fill_n((int*)mat, sizeof(mat)/sizeof(int), 0);
    for(int r = 0; r < H; ++r) {
        for(int c = 0; c < W; ++c) {
            if(front[c] == side[r]) {
                mat[r][c] = max(front[c], side[r]) - 1;
            }
            if(upper[r][c] == 0) {
                mat[r][c] = 0;
            }
        }
    }
    /*
    for(int r = 0; r < H; ++r) {
        for(int c = 0; c < W; ++c) {
            cout << mat[r][c] << ' ';
        }
        cout << endl;
    }
    */
    int res = hungarian(max(H, W), mat);
    cout << acc - res << endl;
    return 0;
}

Submission Info

Submission Time
Task C - Containers
User binding_pry
Language C++11 (GCC 4.8.1)
Score 100
Code Size 5450 Byte
Status AC
Exec Time 31 ms
Memory 1056 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 49
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 4, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 5, 6, 7, 8, 9
Case Name Status Exec Time Memory
1 AC 21 ms 928 KB
10 AC 22 ms 804 KB
11 AC 22 ms 808 KB
12 AC 21 ms 864 KB
13 AC 20 ms 800 KB
14 AC 21 ms 932 KB
15 AC 21 ms 936 KB
16 AC 21 ms 928 KB
17 AC 21 ms 804 KB
18 AC 21 ms 932 KB
19 AC 21 ms 920 KB
2 AC 20 ms 800 KB
20 AC 22 ms 932 KB
21 AC 23 ms 932 KB
22 AC 23 ms 1056 KB
23 AC 23 ms 932 KB
24 AC 23 ms 920 KB
25 AC 22 ms 808 KB
26 AC 23 ms 932 KB
27 AC 22 ms 928 KB
28 AC 23 ms 928 KB
29 AC 22 ms 800 KB
3 AC 21 ms 800 KB
30 AC 21 ms 800 KB
31 AC 22 ms 800 KB
32 AC 24 ms 792 KB
33 AC 22 ms 808 KB
34 AC 20 ms 800 KB
35 AC 21 ms 748 KB
36 AC 21 ms 928 KB
37 AC 21 ms 928 KB
38 AC 21 ms 796 KB
39 AC 21 ms 796 KB
4 AC 21 ms 804 KB
40 AC 21 ms 932 KB
41 AC 21 ms 804 KB
42 AC 27 ms 800 KB
43 AC 22 ms 804 KB
44 AC 22 ms 804 KB
45 AC 21 ms 800 KB
46 AC 22 ms 928 KB
47 AC 21 ms 804 KB
48 AC 20 ms 932 KB
49 AC 23 ms 928 KB
5 AC 21 ms 796 KB
6 AC 31 ms 860 KB
7 AC 20 ms 924 KB
8 AC 21 ms 864 KB
9 AC 23 ms 804 KB