oj.uz

Submission #229160

# Submission time Handle Problem Language Result Execution time Memory
229160 2020-05-03T14:07:21 Z wleung_bvg Skandi (COCI20_skandi) C++17
110 / 110
 298 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) {
        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 11 ms 12416 KB Correct.
4 Correct 12 ms 12416 KB Correct.
5 Correct 12 ms 12288 KB Correct.
6 Correct 12 ms 12416 KB Correct.
7 Correct 12 ms 12416 KB Correct.
8 Correct 12 ms 12288 KB Correct.
9 Correct 13 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 14 ms 12288 KB Correct.
14 Correct 12 ms 12288 KB Correct.
15 Correct 12 ms 12288 KB Correct.
16 Correct 11 ms 12288 KB Correct.
17 Correct 12 ms 12288 KB Correct.
18 Correct 11 ms 12416 KB Correct.
19 Correct 12 ms 12288 KB Correct.
20 Correct 12 ms 12416 KB Correct.
21 Correct 12 ms 12416 KB Correct.
22 Correct 12 ms 12416 KB Correct.
23 Correct 12 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 12 ms 12416 KB Correct.
3 Correct 12 ms 12416 KB Correct.
4 Correct 12 ms 12416 KB Correct.
5 Correct 12 ms 12416 KB Correct.
6 Correct 12 ms 12416 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 12 ms 12416 KB Correct.
9 Correct 13 ms 12544 KB Correct.
10 Correct 13 ms 12672 KB Correct.
11 Correct 13 ms 12800 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 13 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 15 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 14 ms 12672 KB Correct.
26 Correct 14 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 12 ms 12416 KB Correct.
5 Correct 12 ms 12288 KB Correct.
6 Correct 12 ms 12416 KB Correct.
7 Correct 12 ms 12416 KB Correct.
8 Correct 12 ms 12288 KB Correct.
9 Correct 13 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 14 ms 12288 KB Correct.
14 Correct 12 ms 12288 KB Correct.
15 Correct 12 ms 12288 KB Correct.
16 Correct 11 ms 12288 KB Correct.
17 Correct 12 ms 12288 KB Correct.
18 Correct 11 ms 12416 KB Correct.
19 Correct 12 ms 12288 KB Correct.
20 Correct 12 ms 12416 KB Correct.
21 Correct 12 ms 12416 KB Correct.
22 Correct 12 ms 12416 KB Correct.
23 Correct 12 ms 12288 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 12 ms 12416 KB Correct.
28 Correct 12 ms 12416 KB Correct.
29 Correct 12 ms 12416 KB Correct.
30 Correct 11 ms 12416 KB Correct.
31 Correct 12 ms 12416 KB Correct.
32 Correct 13 ms 12544 KB Correct.
33 Correct 13 ms 12672 KB Correct.
34 Correct 13 ms 12800 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 13 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 15 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 14 ms 12672 KB Correct.
49 Correct 14 ms 12672 KB Correct.
50 Correct 86 ms 22760 KB Correct.
51 Correct 252 ms 21448 KB Correct.
52 Correct 140 ms 24044 KB Correct.
53 Correct 88 ms 23008 KB Correct.
54 Correct 114 ms 22508 KB Correct.
55 Correct 112 ms 24164 KB Correct.
56 Correct 87 ms 23912 KB Correct.
57 Correct 85 ms 23656 KB Correct.
58 Correct 298 ms 21744 KB Correct.
59 Correct 89 ms 21860 KB Correct.
60 Correct 106 ms 23404 KB Correct.
61 Correct 159 ms 22460 KB Correct.
62 Correct 98 ms 23404 KB Correct.
63 Correct 97 ms 23524 KB Correct.
64 Correct 107 ms 21496 KB Correct.
65 Correct 98 ms 23528 KB Correct.
66 Correct 134 ms 23152 KB Correct.
67 Correct 158 ms 24172 KB Correct.
68 Correct 113 ms 24168 KB Correct.
69 Correct 103 ms 22888 KB Correct.
70 Correct 100 ms 23140 KB Correct.
71 Correct 170 ms 24864 KB Correct.
72 Correct 88 ms 24552 KB Correct.
73 Correct 160 ms 24836 KB Correct.
74 Correct 211 ms 24692 KB Correct.
75 Correct 153 ms 24936 KB Correct.