oj.uz

Submission #229158

# Submission time Handle Problem Language Result Execution time Memory
229158 2020-05-03T14:01:16 Z wleung_bvg Skandi (COCI20_skandi) C++17
110 / 110
 271 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 + 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) {
        if (lvl[v] == -1) return false;
        int l = lvl[v]; lvl[v] = -1;
        for (int w : adj[v]) if (lvl[mate[w]] == l + 1 && (mate[w] == V || dfs(V, mate[w]))) { mate[mate[v] = w] = v; return true; }
        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 11 ms 12416 KB Correct.
2 Correct 11 ms 12288 KB Correct.
3 Correct 11 ms 12320 KB Correct.
4 Correct 11 ms 12288 KB Correct.
5 Correct 11 ms 12288 KB Correct.
6 Correct 12 ms 12416 KB Correct.
7 Correct 12 ms 12416 KB Correct.
8 Correct 12 ms 12416 KB Correct.
9 Correct 11 ms 12416 KB Correct.
10 Correct 12 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 12 ms 12288 KB Correct.
18 Correct 12 ms 12416 KB Correct.
19 Correct 11 ms 12288 KB Correct.
20 Correct 12 ms 12288 KB Correct.
21 Correct 11 ms 12416 KB Correct.
22 Correct 11 ms 12288 KB Correct.
23 Correct 11 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 13 ms 12416 KB Correct.
3 Correct 15 ms 12416 KB Correct.
4 Correct 13 ms 12416 KB Correct.
5 Correct 12 ms 12416 KB Correct.
6 Correct 12 ms 12416 KB Correct.
7 Correct 13 ms 12416 KB Correct.
8 Correct 12 ms 12416 KB Correct.
9 Correct 12 ms 12648 KB Correct.
10 Correct 13 ms 12672 KB Correct.
11 Correct 13 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 12 ms 12672 KB Correct.
16 Correct 12 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 13 ms 12672 KB Correct.
22 Correct 13 ms 12696 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 13 ms 12672 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12416 KB Correct.
2 Correct 11 ms 12288 KB Correct.
3 Correct 11 ms 12320 KB Correct.
4 Correct 11 ms 12288 KB Correct.
5 Correct 11 ms 12288 KB Correct.
6 Correct 12 ms 12416 KB Correct.
7 Correct 12 ms 12416 KB Correct.
8 Correct 12 ms 12416 KB Correct.
9 Correct 11 ms 12416 KB Correct.
10 Correct 12 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 12 ms 12288 KB Correct.
18 Correct 12 ms 12416 KB Correct.
19 Correct 11 ms 12288 KB Correct.
20 Correct 12 ms 12288 KB Correct.
21 Correct 11 ms 12416 KB Correct.
22 Correct 11 ms 12288 KB Correct.
23 Correct 11 ms 12416 KB Correct.
24 Correct 11 ms 12416 KB Correct.
25 Correct 13 ms 12416 KB Correct.
26 Correct 15 ms 12416 KB Correct.
27 Correct 13 ms 12416 KB Correct.
28 Correct 12 ms 12416 KB Correct.
29 Correct 12 ms 12416 KB Correct.
30 Correct 13 ms 12416 KB Correct.
31 Correct 12 ms 12416 KB Correct.
32 Correct 12 ms 12648 KB Correct.
33 Correct 13 ms 12672 KB Correct.
34 Correct 13 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 12 ms 12672 KB Correct.
39 Correct 12 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 13 ms 12672 KB Correct.
45 Correct 13 ms 12696 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 13 ms 12672 KB Correct.
50 Correct 83 ms 22756 KB Correct.
51 Correct 235 ms 21616 KB Correct.
52 Correct 142 ms 24044 KB Correct.
53 Correct 82 ms 22992 KB Correct.
54 Correct 105 ms 22512 KB Correct.
55 Correct 108 ms 24248 KB Correct.
56 Correct 81 ms 23908 KB Correct.
57 Correct 79 ms 23532 KB Correct.
58 Correct 271 ms 21736 KB Correct.
59 Correct 82 ms 21988 KB Correct.
60 Correct 92 ms 23396 KB Correct.
61 Correct 134 ms 22380 KB Correct.
62 Correct 92 ms 23388 KB Correct.
63 Correct 94 ms 23528 KB Correct.
64 Correct 102 ms 21300 KB Correct.
65 Correct 84 ms 23400 KB Correct.
66 Correct 130 ms 23148 KB Correct.
67 Correct 150 ms 24172 KB Correct.
68 Correct 110 ms 24172 KB Correct.
69 Correct 92 ms 22888 KB Correct.
70 Correct 92 ms 23148 KB Correct.
71 Correct 156 ms 24684 KB Correct.
72 Correct 93 ms 24556 KB Correct.
73 Correct 133 ms 24808 KB Correct.
74 Correct 150 ms 24680 KB Correct.
75 Correct 131 ms 24936 KB Correct.