oj.uz

Submission #229152

# Submission time Handle Problem Language Result Execution time Memory
229152 2020-05-03T13:25:14 Z wleung_bvg Skandi (COCI20_skandi) C++17
110 / 110
 290 ms 25192 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 {
    const int NONE = MAXV; 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() {
        lvl[NONE] = -1; int front = 0, back = 0;
        for (int v : type[0]) {
            if (mate[v] == NONE) 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] != NONE) q[back++] = mate[w];
            }
        }
        return lvl[NONE] != -1;
    }
    bool dfs(int v) {
        for (int w : adj[v]) if (lvl[mate[w]] == lvl[v] + 1 && (mate[w] == NONE || 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] = NONE; }
        while (bfs()) for (int v : type[0]) if (mate[v] == NONE && 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] == NONE) 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 12416 KB Correct.
4 Correct 12 ms 12288 KB Correct.
5 Correct 11 ms 12416 KB Correct.
6 Correct 11 ms 12416 KB Correct.
7 Correct 11 ms 12288 KB Correct.
8 Correct 11 ms 12416 KB Correct.
9 Correct 12 ms 12288 KB Correct.
10 Correct 12 ms 12416 KB Correct.
11 Correct 11 ms 12416 KB Correct.
12 Correct 12 ms 12288 KB Correct.
13 Correct 11 ms 12416 KB Correct.
14 Correct 11 ms 12416 KB Correct.
15 Correct 11 ms 12288 KB Correct.
16 Correct 11 ms 12416 KB Correct.
17 Correct 11 ms 12288 KB Correct.
18 Correct 14 ms 12416 KB Correct.
19 Correct 12 ms 12416 KB Correct.
20 Correct 12 ms 12416 KB Correct.
21 Correct 11 ms 12288 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 12 ms 12416 KB Correct.
2 Correct 12 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 12 ms 12416 KB Correct.
8 Correct 12 ms 12416 KB Correct.
9 Correct 13 ms 12672 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 14 ms 12648 KB Correct.
14 Correct 14 ms 12672 KB Correct.
15 Correct 13 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 13 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 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 12 ms 12416 KB Correct.
4 Correct 12 ms 12288 KB Correct.
5 Correct 11 ms 12416 KB Correct.
6 Correct 11 ms 12416 KB Correct.
7 Correct 11 ms 12288 KB Correct.
8 Correct 11 ms 12416 KB Correct.
9 Correct 12 ms 12288 KB Correct.
10 Correct 12 ms 12416 KB Correct.
11 Correct 11 ms 12416 KB Correct.
12 Correct 12 ms 12288 KB Correct.
13 Correct 11 ms 12416 KB Correct.
14 Correct 11 ms 12416 KB Correct.
15 Correct 11 ms 12288 KB Correct.
16 Correct 11 ms 12416 KB Correct.
17 Correct 11 ms 12288 KB Correct.
18 Correct 14 ms 12416 KB Correct.
19 Correct 12 ms 12416 KB Correct.
20 Correct 12 ms 12416 KB Correct.
21 Correct 11 ms 12288 KB Correct.
22 Correct 11 ms 12416 KB Correct.
23 Correct 11 ms 12288 KB Correct.
24 Correct 12 ms 12416 KB Correct.
25 Correct 12 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 12 ms 12416 KB Correct.
31 Correct 12 ms 12416 KB Correct.
32 Correct 13 ms 12672 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 14 ms 12648 KB Correct.
37 Correct 14 ms 12672 KB Correct.
38 Correct 13 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 13 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 12 ms 12672 KB Correct.
50 Correct 88 ms 22760 KB Correct.
51 Correct 276 ms 21592 KB Correct.
52 Correct 152 ms 24300 KB Correct.
53 Correct 83 ms 23264 KB Correct.
54 Correct 114 ms 22760 KB Correct.
55 Correct 109 ms 24296 KB Correct.
56 Correct 86 ms 24164 KB Correct.
57 Correct 80 ms 23832 KB Correct.
58 Correct 290 ms 21936 KB Correct.
59 Correct 84 ms 22240 KB Correct.
60 Correct 105 ms 23528 KB Correct.
61 Correct 149 ms 22640 KB Correct.
62 Correct 94 ms 23784 KB Correct.
63 Correct 98 ms 23780 KB Correct.
64 Correct 104 ms 21624 KB Correct.
65 Correct 93 ms 23660 KB Correct.
66 Correct 138 ms 23276 KB Correct.
67 Correct 165 ms 24508 KB Correct.
68 Correct 113 ms 24428 KB Correct.
69 Correct 97 ms 23208 KB Correct.
70 Correct 98 ms 23276 KB Correct.
71 Correct 164 ms 24944 KB Correct.
72 Correct 92 ms 24812 KB Correct.
73 Correct 140 ms 25192 KB Correct.
74 Correct 163 ms 24936 KB Correct.
75 Correct 138 ms 25192 KB Correct.