oj.uz

Submission #229162

# Submission time Handle Problem Language Result Execution time Memory
229162 2020-05-03T14:19:00 Z wleung_bvg Skandi (COCI20_skandi) C++17
110 / 110
 222 ms 24936 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], 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 front = 0, back = 0;
        for (int v : type[0]) {
            if (mate[v] == -1) lvl[q[back++] = v] = 0;
            else lvl[v] = -1;
        }
        while (front < back) {
            int v = q[front++];
            for (int w : adj[v]) {
                if (mate[w] == -1) return true;
                else if (lvl[mate[w]] == -1) lvl[q[back++] = mate[w]] = lvl[v] + 1;
            }
        }
        return false;
    }
    bool dfs(int v) {
        for (int w : adj[v]) if (mate[w] == -1 || (lvl[mate[w]] == lvl[v] + 1 && dfs(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] = -1; }
        while (bfs()) for (int v : type[0]) if (mate[v] == -1 && dfs(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] == -1) 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 11 ms 12416 KB Correct.
4 Correct 11 ms 12288 KB Correct.
5 Correct 11 ms 12288 KB Correct.
6 Correct 11 ms 12288 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 11 ms 12416 KB Correct.
9 Correct 11 ms 12416 KB Correct.
10 Correct 11 ms 12416 KB Correct.
11 Correct 11 ms 12416 KB Correct.
12 Correct 11 ms 12416 KB Correct.
13 Correct 11 ms 12416 KB Correct.
14 Correct 11 ms 12416 KB Correct.
15 Correct 11 ms 12416 KB Correct.
16 Correct 11 ms 12416 KB Correct.
17 Correct 11 ms 12416 KB Correct.
18 Correct 11 ms 12288 KB Correct.
19 Correct 11 ms 12288 KB Correct.
20 Correct 11 ms 12416 KB Correct.
21 Correct 11 ms 12416 KB Correct.
22 Correct 11 ms 12288 KB Correct.
23 Correct 11 ms 12288 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12416 KB Correct.
2 Correct 11 ms 12416 KB Correct.
3 Correct 11 ms 12416 KB Correct.
4 Correct 11 ms 12416 KB Correct.
5 Correct 11 ms 12416 KB Correct.
6 Correct 12 ms 12416 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 11 ms 12416 KB Correct.
9 Correct 13 ms 12544 KB Correct.
10 Correct 13 ms 12672 KB Correct.
11 Correct 12 ms 12672 KB Correct.
12 Correct 12 ms 12672 KB Correct.
13 Correct 12 ms 12672 KB Correct.
14 Correct 13 ms 12672 KB Correct.
15 Correct 12 ms 12672 KB Correct.
16 Correct 13 ms 12672 KB Correct.
17 Correct 13 ms 12672 KB Correct.
18 Correct 13 ms 12672 KB Correct.
19 Correct 13 ms 12672 KB Correct.
20 Correct 13 ms 12672 KB Correct.
21 Correct 12 ms 12672 KB Correct.
22 Correct 12 ms 12672 KB Correct.
23 Correct 13 ms 12672 KB Correct.
24 Correct 12 ms 12672 KB Correct.
25 Correct 13 ms 12672 KB Correct.
26 Correct 12 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 11 ms 12416 KB Correct.
4 Correct 11 ms 12288 KB Correct.
5 Correct 11 ms 12288 KB Correct.
6 Correct 11 ms 12288 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 11 ms 12416 KB Correct.
9 Correct 11 ms 12416 KB Correct.
10 Correct 11 ms 12416 KB Correct.
11 Correct 11 ms 12416 KB Correct.
12 Correct 11 ms 12416 KB Correct.
13 Correct 11 ms 12416 KB Correct.
14 Correct 11 ms 12416 KB Correct.
15 Correct 11 ms 12416 KB Correct.
16 Correct 11 ms 12416 KB Correct.
17 Correct 11 ms 12416 KB Correct.
18 Correct 11 ms 12288 KB Correct.
19 Correct 11 ms 12288 KB Correct.
20 Correct 11 ms 12416 KB Correct.
21 Correct 11 ms 12416 KB Correct.
22 Correct 11 ms 12288 KB Correct.
23 Correct 11 ms 12288 KB Correct.
24 Correct 11 ms 12416 KB Correct.
25 Correct 11 ms 12416 KB Correct.
26 Correct 11 ms 12416 KB Correct.
27 Correct 11 ms 12416 KB Correct.
28 Correct 11 ms 12416 KB Correct.
29 Correct 12 ms 12416 KB Correct.
30 Correct 11 ms 12416 KB Correct.
31 Correct 11 ms 12416 KB Correct.
32 Correct 13 ms 12544 KB Correct.
33 Correct 13 ms 12672 KB Correct.
34 Correct 12 ms 12672 KB Correct.
35 Correct 12 ms 12672 KB Correct.
36 Correct 12 ms 12672 KB Correct.
37 Correct 13 ms 12672 KB Correct.
38 Correct 12 ms 12672 KB Correct.
39 Correct 13 ms 12672 KB Correct.
40 Correct 13 ms 12672 KB Correct.
41 Correct 13 ms 12672 KB Correct.
42 Correct 13 ms 12672 KB Correct.
43 Correct 13 ms 12672 KB Correct.
44 Correct 12 ms 12672 KB Correct.
45 Correct 12 ms 12672 KB Correct.
46 Correct 13 ms 12672 KB Correct.
47 Correct 12 ms 12672 KB Correct.
48 Correct 13 ms 12672 KB Correct.
49 Correct 12 ms 12672 KB Correct.
50 Correct 85 ms 22864 KB Correct.
51 Correct 208 ms 21488 KB Correct.
52 Correct 135 ms 24044 KB Correct.
53 Correct 79 ms 23008 KB Correct.
54 Correct 109 ms 22508 KB Correct.
55 Correct 108 ms 24040 KB Correct.
56 Correct 84 ms 24036 KB Correct.
57 Correct 75 ms 23528 KB Correct.
58 Correct 222 ms 21724 KB Correct.
59 Correct 81 ms 21864 KB Correct.
60 Correct 94 ms 23396 KB Correct.
61 Correct 134 ms 22380 KB Correct.
62 Correct 87 ms 23396 KB Correct.
63 Correct 91 ms 23528 KB Correct.
64 Correct 98 ms 21336 KB Correct.
65 Correct 89 ms 23400 KB Correct.
66 Correct 125 ms 23152 KB Correct.
67 Correct 141 ms 24296 KB Correct.
68 Correct 110 ms 24176 KB Correct.
69 Correct 89 ms 22888 KB Correct.
70 Correct 87 ms 23148 KB Correct.
71 Correct 143 ms 24936 KB Correct.
72 Correct 88 ms 24560 KB Correct.
73 Correct 132 ms 24804 KB Correct.
74 Correct 148 ms 24680 KB Correct.
75 Correct 127 ms 24936 KB Correct.