oj.uz

Submission #229156

# Submission time Handle Problem Language Result Execution time Memory
229156 2020-05-03T13:53:18 Z wleung_bvg Skandi (COCI20_skandi) C++17
110 / 110
 289 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) 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 11 ms 12288 KB Correct.
2 Correct 11 ms 12288 KB Correct.
3 Correct 11 ms 12288 KB Correct.
4 Correct 11 ms 12416 KB Correct.
5 Correct 11 ms 12416 KB Correct.
6 Correct 11 ms 12416 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 11 ms 12416 KB Correct.
9 Correct 11 ms 12288 KB Correct.
10 Correct 10 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 12 ms 12416 KB Correct.
15 Correct 10 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 12 ms 12416 KB Correct.
20 Correct 11 ms 12416 KB Correct.
21 Correct 11 ms 12416 KB Correct.
22 Correct 11 ms 12416 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 12 ms 12416 KB Correct.
6 Correct 11 ms 12416 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 12 ms 12416 KB Correct.
9 Correct 14 ms 12672 KB Correct.
10 Correct 12 ms 12672 KB Correct.
11 Correct 12 ms 12672 KB Correct.
12 Correct 13 ms 12672 KB Correct.
13 Correct 13 ms 12672 KB Correct.
14 Correct 12 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 12 ms 12672 KB Correct.
20 Correct 13 ms 12672 KB Correct.
21 Correct 13 ms 12672 KB Correct.
22 Correct 13 ms 12672 KB Correct.
23 Correct 12 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 11 ms 12288 KB Correct.
2 Correct 11 ms 12288 KB Correct.
3 Correct 11 ms 12288 KB Correct.
4 Correct 11 ms 12416 KB Correct.
5 Correct 11 ms 12416 KB Correct.
6 Correct 11 ms 12416 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 11 ms 12416 KB Correct.
9 Correct 11 ms 12288 KB Correct.
10 Correct 10 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 12 ms 12416 KB Correct.
15 Correct 10 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 12 ms 12416 KB Correct.
20 Correct 11 ms 12416 KB Correct.
21 Correct 11 ms 12416 KB Correct.
22 Correct 11 ms 12416 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 12 ms 12416 KB Correct.
29 Correct 11 ms 12416 KB Correct.
30 Correct 11 ms 12416 KB Correct.
31 Correct 12 ms 12416 KB Correct.
32 Correct 14 ms 12672 KB Correct.
33 Correct 12 ms 12672 KB Correct.
34 Correct 12 ms 12672 KB Correct.
35 Correct 13 ms 12672 KB Correct.
36 Correct 13 ms 12672 KB Correct.
37 Correct 12 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 12 ms 12672 KB Correct.
43 Correct 13 ms 12672 KB Correct.
44 Correct 13 ms 12672 KB Correct.
45 Correct 13 ms 12672 KB Correct.
46 Correct 12 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 87 ms 22780 KB Correct.
51 Correct 289 ms 21552 KB Correct.
52 Correct 144 ms 24040 KB Correct.
53 Correct 87 ms 23008 KB Correct.
54 Correct 114 ms 22592 KB Correct.
55 Correct 110 ms 24044 KB Correct.
56 Correct 84 ms 23908 KB Correct.
57 Correct 80 ms 23656 KB Correct.
58 Correct 274 ms 21744 KB Correct.
59 Correct 85 ms 21992 KB Correct.
60 Correct 105 ms 23400 KB Correct.
61 Correct 148 ms 22376 KB Correct.
62 Correct 95 ms 23404 KB Correct.
63 Correct 93 ms 23536 KB Correct.
64 Correct 101 ms 21340 KB Correct.
65 Correct 89 ms 23400 KB Correct.
66 Correct 140 ms 23152 KB Correct.
67 Correct 163 ms 24168 KB Correct.
68 Correct 108 ms 24296 KB Correct.
69 Correct 96 ms 22888 KB Correct.
70 Correct 93 ms 23144 KB Correct.
71 Correct 159 ms 24812 KB Correct.
72 Correct 87 ms 24560 KB Correct.
73 Correct 132 ms 24812 KB Correct.
74 Correct 173 ms 24680 KB Correct.
75 Correct 130 ms 24936 KB Correct.