oj.uz

Submission #229159

# Submission time Handle Problem Language Result Execution time Memory
229159 2020-05-03T14:06:54 Z wleung_bvg Skandi (COCI20_skandi) C++17
110 / 110
 282 ms 24912 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 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 11 ms 12416 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 11 ms 12416 KB Correct.
9 Correct 13 ms 12416 KB Correct.
10 Correct 11 ms 12288 KB Correct.
11 Correct 12 ms 12416 KB Correct.
12 Correct 11 ms 12416 KB Correct.
13 Correct 13 ms 12416 KB Correct.
14 Correct 12 ms 12288 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 12 ms 12416 KB Correct.
19 Correct 12 ms 12416 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 13 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 13 ms 12416 KB Correct.
5 Correct 12 ms 12416 KB Correct.
6 Correct 13 ms 12416 KB Correct.
7 Correct 12 ms 12416 KB Correct.
8 Correct 12 ms 12544 KB Correct.
9 Correct 14 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 13 ms 12672 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 15 ms 12576 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 14 ms 12672 KB Correct.
23 Correct 14 ms 12672 KB Correct.
24 Correct 18 ms 12672 KB Correct.
25 Correct 19 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 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 11 ms 12416 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 11 ms 12416 KB Correct.
9 Correct 13 ms 12416 KB Correct.
10 Correct 11 ms 12288 KB Correct.
11 Correct 12 ms 12416 KB Correct.
12 Correct 11 ms 12416 KB Correct.
13 Correct 13 ms 12416 KB Correct.
14 Correct 12 ms 12288 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 12 ms 12416 KB Correct.
19 Correct 12 ms 12416 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 13 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 13 ms 12416 KB Correct.
28 Correct 12 ms 12416 KB Correct.
29 Correct 13 ms 12416 KB Correct.
30 Correct 12 ms 12416 KB Correct.
31 Correct 12 ms 12544 KB Correct.
32 Correct 14 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 13 ms 12672 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 15 ms 12576 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 14 ms 12672 KB Correct.
46 Correct 14 ms 12672 KB Correct.
47 Correct 18 ms 12672 KB Correct.
48 Correct 19 ms 12672 KB Correct.
49 Correct 13 ms 12672 KB Correct.
50 Correct 105 ms 22888 KB Correct.
51 Correct 254 ms 21508 KB Correct.
52 Correct 153 ms 24168 KB Correct.
53 Correct 87 ms 23004 KB Correct.
54 Correct 120 ms 22488 KB Correct.
55 Correct 120 ms 24168 KB Correct.
56 Correct 89 ms 23888 KB Correct.
57 Correct 81 ms 23528 KB Correct.
58 Correct 282 ms 21992 KB Correct.
59 Correct 90 ms 21860 KB Correct.
60 Correct 99 ms 23400 KB Correct.
61 Correct 152 ms 22516 KB Correct.
62 Correct 106 ms 23400 KB Correct.
63 Correct 101 ms 23532 KB Correct.
64 Correct 130 ms 21368 KB Correct.
65 Correct 97 ms 23404 KB Correct.
66 Correct 140 ms 23196 KB Correct.
67 Correct 168 ms 24168 KB Correct.
68 Correct 114 ms 24172 KB Correct.
69 Correct 103 ms 22892 KB Correct.
70 Correct 106 ms 23144 KB Correct.
71 Correct 173 ms 24684 KB Correct.
72 Correct 94 ms 24552 KB Correct.
73 Correct 142 ms 24812 KB Correct.
74 Correct 172 ms 24684 KB Correct.
75 Correct 139 ms 24912 KB Correct.