oj.uz

Submission #229157

# Submission time Handle Problem Language Result Execution time Memory
229157 2020-05-03T13:55:58 Z wleung_bvg Skandi (COCI20_skandi) C++17
110 / 110
 276 ms 25008 KB 
#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int sz(const C&c){return int(c.size());}
using ll=long long;constexpr const char nl='\n',sp=' ';

template <const int MAXV> struct HopcroftKarpMaxMatch {
    int mate[MAXV], lvl[MAXV + 1], q[MAXV]; vector<int> adj[MAXV], type[2]; bool color[MAXV], inCover[MAXV], vis[MAXV];
    void addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); }
    bool bfs(int V) {
        lvl[V] = -1; int front = 0, back = 0;
        for (int v : type[0]) {
            if (mate[v] == V) lvl[q[back++] = v] = 0;
            else lvl[v] = -1;
        }
        while (front < back) {
            int v = q[front++];
            for (int w : adj[v]) if (lvl[mate[w]] == -1) {
                lvl[mate[w]] = lvl[v] + 1;
                if (mate[w] == V) return true;
                else q[back++] = mate[w];
            }
        }
        return lvl[V] != -1;
    }
    bool dfs(int V, int v) {
        for (int w : adj[v]) if (lvl[mate[w]] == lvl[v] + 1 && (mate[w] == V || dfs(V, mate[w]))) { mate[mate[v] = w] = v; return true; }
        lvl[v] = -1; return false;
    }
    void init(int V) { for (int i = 0; i < V; i++) { adj[i].clear(); color[i] = false; } }
    int getMaxMatch(int V) {
        int cardinality = 0;
        for (int i = 0; i < 2; i++) type[i].clear();
        for (int v = 0; v < V; v++) { type[color[v]].push_back(v); mate[v] = V; }
        while (bfs(V)) for (int v : type[0]) if (mate[v] == V && dfs(V, v)) cardinality++;
        return cardinality;
    }
    void dfsVertexCover(int v) {
        if (vis[v]) return;
        vis[v] = true;
        for (int w : adj[v]) if ((mate[v] == w) == color[v]) dfsVertexCover(w);
    }
    void getVertexCover(int V) {
        fill(vis, vis + V, false);
        for (int v : type[0]) if (mate[v] == V) dfsVertexCover(v);
        for (int v = 0; v < V; v++) inCover[v] = vis[v] == color[v];
    }
};

const int MAXNM = 505;

int N, M;
string G[MAXNM];
HopcroftKarpMaxMatch<MAXNM * MAXNM * 2> mm;

int getUp(int i, int j) {
    if (G[i][j] == '1') return i * M + j;
    return getUp(i - 1, j);
}

int getLeft(int i, int j) {
    if (G[i][j] == '1') return N * M + i * M + j;
    return getLeft(i, j - 1);
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // freopen("err.txt", "w", stderr);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    mm.init(N * M * 2);
    fill(mm.color, mm.color + N * M, true);
    for (int i = 0; i < N; i++) cin >> G[i];
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (G[i][j] == '0') mm.addEdge(getUp(i, j), getLeft(i, j));
    cout << mm.getMaxMatch(N * M * 2) << nl;
    mm.getVertexCover(N * M * 2);
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (G[i][j] == '1') {
        if (mm.inCover[i * M + j] && mm.mate[i * M + j] != -1) cout << i + 1 << sp << j + 1 << sp << "DOLJE" << nl;
        if (mm.inCover[N * M + i * M + j] && mm.mate[N * M + i * M + j] != -1) cout << i + 1 << sp << j + 1 << sp << "DESNO" << nl;
    }
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12416 KB Correct.
2 Correct 11 ms 12416 KB Correct.
3 Correct 12 ms 12288 KB Correct.
4 Correct 12 ms 12288 KB Correct.
5 Correct 12 ms 12416 KB Correct.
6 Correct 12 ms 12288 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 12 ms 12416 KB Correct.
9 Correct 12 ms 12288 KB Correct.
10 Correct 12 ms 12416 KB Correct.
11 Correct 12 ms 12416 KB Correct.
12 Correct 12 ms 12288 KB Correct.
13 Correct 12 ms 12416 KB Correct.
14 Correct 13 ms 12416 KB Correct.
15 Correct 13 ms 12416 KB Correct.
16 Correct 12 ms 12544 KB Correct.
17 Correct 12 ms 12288 KB Correct.
18 Correct 13 ms 12416 KB Correct.
19 Correct 12 ms 12416 KB Correct.
20 Correct 12 ms 12416 KB Correct.
21 Correct 12 ms 12288 KB Correct.
22 Correct 13 ms 12416 KB Correct.
23 Correct 13 ms 12416 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12416 KB Correct.
2 Correct 12 ms 12416 KB Correct.
3 Correct 12 ms 12416 KB Correct.
4 Correct 13 ms 12416 KB Correct.
5 Correct 12 ms 12416 KB Correct.
6 Correct 13 ms 12416 KB Correct.
7 Correct 12 ms 12416 KB Correct.
8 Correct 12 ms 12416 KB Correct.
9 Correct 13 ms 12544 KB Correct.
10 Correct 14 ms 12672 KB Correct.
11 Correct 14 ms 12672 KB Correct.
12 Correct 13 ms 12672 KB Correct.
13 Correct 13 ms 12672 KB Correct.
14 Correct 13 ms 12672 KB Correct.
15 Correct 14 ms 12672 KB Correct.
16 Correct 13 ms 12672 KB Correct.
17 Correct 14 ms 12672 KB Correct.
18 Correct 13 ms 12672 KB Correct.
19 Correct 14 ms 12672 KB Correct.
20 Correct 14 ms 12648 KB Correct.
21 Correct 14 ms 12672 KB Correct.
22 Correct 13 ms 12672 KB Correct.
23 Correct 13 ms 12672 KB Correct.
24 Correct 13 ms 12672 KB Correct.
25 Correct 13 ms 12672 KB Correct.
26 Correct 13 ms 12672 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12416 KB Correct.
2 Correct 11 ms 12416 KB Correct.
3 Correct 12 ms 12288 KB Correct.
4 Correct 12 ms 12288 KB Correct.
5 Correct 12 ms 12416 KB Correct.
6 Correct 12 ms 12288 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 12 ms 12416 KB Correct.
9 Correct 12 ms 12288 KB Correct.
10 Correct 12 ms 12416 KB Correct.
11 Correct 12 ms 12416 KB Correct.
12 Correct 12 ms 12288 KB Correct.
13 Correct 12 ms 12416 KB Correct.
14 Correct 13 ms 12416 KB Correct.
15 Correct 13 ms 12416 KB Correct.
16 Correct 12 ms 12544 KB Correct.
17 Correct 12 ms 12288 KB Correct.
18 Correct 13 ms 12416 KB Correct.
19 Correct 12 ms 12416 KB Correct.
20 Correct 12 ms 12416 KB Correct.
21 Correct 12 ms 12288 KB Correct.
22 Correct 13 ms 12416 KB Correct.
23 Correct 13 ms 12416 KB Correct.
24 Correct 11 ms 12416 KB Correct.
25 Correct 12 ms 12416 KB Correct.
26 Correct 12 ms 12416 KB Correct.
27 Correct 13 ms 12416 KB Correct.
28 Correct 12 ms 12416 KB Correct.
29 Correct 13 ms 12416 KB Correct.
30 Correct 12 ms 12416 KB Correct.
31 Correct 12 ms 12416 KB Correct.
32 Correct 13 ms 12544 KB Correct.
33 Correct 14 ms 12672 KB Correct.
34 Correct 14 ms 12672 KB Correct.
35 Correct 13 ms 12672 KB Correct.
36 Correct 13 ms 12672 KB Correct.
37 Correct 13 ms 12672 KB Correct.
38 Correct 14 ms 12672 KB Correct.
39 Correct 13 ms 12672 KB Correct.
40 Correct 14 ms 12672 KB Correct.
41 Correct 13 ms 12672 KB Correct.
42 Correct 14 ms 12672 KB Correct.
43 Correct 14 ms 12648 KB Correct.
44 Correct 14 ms 12672 KB Correct.
45 Correct 13 ms 12672 KB Correct.
46 Correct 13 ms 12672 KB Correct.
47 Correct 13 ms 12672 KB Correct.
48 Correct 13 ms 12672 KB Correct.
49 Correct 13 ms 12672 KB Correct.
50 Correct 84 ms 22764 KB Correct.
51 Correct 262 ms 21640 KB Correct.
52 Correct 145 ms 24040 KB Correct.
53 Correct 83 ms 23004 KB Correct.
54 Correct 113 ms 22640 KB Correct.
55 Correct 113 ms 24168 KB Correct.
56 Correct 84 ms 23908 KB Correct.
57 Correct 80 ms 23528 KB Correct.
58 Correct 276 ms 21864 KB Correct.
59 Correct 85 ms 21860 KB Correct.
60 Correct 98 ms 23400 KB Correct.
61 Correct 145 ms 22424 KB Correct.
62 Correct 96 ms 23400 KB Correct.
63 Correct 90 ms 23528 KB Correct.
64 Correct 105 ms 21368 KB Correct.
65 Correct 104 ms 23400 KB Correct.
66 Correct 138 ms 23152 KB Correct.
67 Correct 177 ms 24196 KB Correct.
68 Correct 115 ms 24176 KB Correct.
69 Correct 101 ms 22884 KB Correct.
70 Correct 100 ms 23144 KB Correct.
71 Correct 159 ms 24832 KB Correct.
72 Correct 91 ms 24552 KB Correct.
73 Correct 136 ms 24808 KB Correct.
74 Correct 167 ms 24680 KB Correct.
75 Correct 154 ms 25008 KB Correct.