Japan Alumni Group Summer Camp 2013 Warming Up

Submission #102014

Source codeソースコード

#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

Task問題 C - Containers
User nameユーザ名 あずにゃん vs. binding.pry
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 5450 Byte
File nameファイル名
Exec time実行時間 31 ms
Memory usageメモリ使用量 1056 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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