oj.uz

Submission #229155

# Submission time Handle Problem Language Result Execution time Memory
229155 2020-05-03T13:43:58 Z wleung_bvg Skandi (COCI20_skandi) C++17
110 / 110
 206 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], 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 front = 0, back = 0; bool hasPath = false;
        for (int v : type[0]) {
            if (mate[v] == -1) lvl[q[back++] = v] = 0;
            else lvl[v] = -1;
        }
        while (front < back) {
            int v = q[front++];
            for (int w : adj[v]) {
                if (mate[w] == -1) hasPath = true;
                else if (lvl[mate[w]] == -1) lvl[q[back++] = mate[w]] = lvl[v] + 1;
            }
        }
        return hasPath;
    }
    bool dfs(int v) {
        for (int w : adj[v]) if (mate[w] == -1 || (lvl[mate[w]] == lvl[v] + 1 && 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] = -1; }
        while (bfs()) for (int v : type[0]) if (mate[v] == -1 && 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] == -1) 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 12416 KB Correct.
4 Correct 11 ms 12416 KB Correct.
5 Correct 11 ms 12288 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 11 ms 12416 KB Correct.
10 Correct 11 ms 12416 KB Correct.
11 Correct 11 ms 12416 KB Correct.
12 Correct 11 ms 12416 KB Correct.
13 Correct 11 ms 12288 KB Correct.
14 Correct 11 ms 12416 KB Correct.
15 Correct 12 ms 12416 KB Correct.
16 Correct 11 ms 12416 KB Correct.
17 Correct 11 ms 12416 KB Correct.
18 Correct 11 ms 12416 KB Correct.
19 Correct 11 ms 12416 KB Correct.
20 Correct 12 ms 12416 KB Correct.
21 Correct 13 ms 12416 KB Correct.
22 Correct 11 ms 12416 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 12 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 12 ms 12416 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 13 ms 12544 KB Correct.
9 Correct 12 ms 12672 KB Correct.
10 Correct 12 ms 12672 KB Correct.
11 Correct 13 ms 12672 KB Correct.
12 Correct 12 ms 12672 KB Correct.
13 Correct 12 ms 12672 KB Correct.
14 Correct 12 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 12 ms 12672 KB Correct.
19 Correct 12 ms 12672 KB Correct.
20 Correct 13 ms 12672 KB Correct.
21 Correct 12 ms 12672 KB Correct.
22 Correct 12 ms 12672 KB Correct.
23 Correct 12 ms 12672 KB Correct.
24 Correct 12 ms 12672 KB Correct.
25 Correct 12 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 12416 KB Correct.
4 Correct 11 ms 12416 KB Correct.
5 Correct 11 ms 12288 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 11 ms 12416 KB Correct.
10 Correct 11 ms 12416 KB Correct.
11 Correct 11 ms 12416 KB Correct.
12 Correct 11 ms 12416 KB Correct.
13 Correct 11 ms 12288 KB Correct.
14 Correct 11 ms 12416 KB Correct.
15 Correct 12 ms 12416 KB Correct.
16 Correct 11 ms 12416 KB Correct.
17 Correct 11 ms 12416 KB Correct.
18 Correct 11 ms 12416 KB Correct.
19 Correct 11 ms 12416 KB Correct.
20 Correct 12 ms 12416 KB Correct.
21 Correct 13 ms 12416 KB Correct.
22 Correct 11 ms 12416 KB Correct.
23 Correct 11 ms 12416 KB Correct.
24 Correct 11 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 11 ms 12416 KB Correct.
29 Correct 12 ms 12416 KB Correct.
30 Correct 11 ms 12416 KB Correct.
31 Correct 13 ms 12544 KB Correct.
32 Correct 12 ms 12672 KB Correct.
33 Correct 12 ms 12672 KB Correct.
34 Correct 13 ms 12672 KB Correct.
35 Correct 12 ms 12672 KB Correct.
36 Correct 12 ms 12672 KB Correct.
37 Correct 12 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 12 ms 12672 KB Correct.
42 Correct 12 ms 12672 KB Correct.
43 Correct 13 ms 12672 KB Correct.
44 Correct 12 ms 12672 KB Correct.
45 Correct 12 ms 12672 KB Correct.
46 Correct 12 ms 12672 KB Correct.
47 Correct 12 ms 12672 KB Correct.
48 Correct 12 ms 12672 KB Correct.
49 Correct 13 ms 12672 KB Correct.
50 Correct 68 ms 22884 KB Correct.
51 Correct 159 ms 21484 KB Correct.
52 Correct 105 ms 24040 KB Correct.
53 Correct 66 ms 23004 KB Correct.
54 Correct 80 ms 22508 KB Correct.
55 Correct 82 ms 24164 KB Correct.
56 Correct 72 ms 23912 KB Correct.
57 Correct 67 ms 23524 KB Correct.
58 Correct 206 ms 21864 KB Correct.
59 Correct 68 ms 21860 KB Correct.
60 Correct 75 ms 23400 KB Correct.
61 Correct 91 ms 22376 KB Correct.
62 Correct 74 ms 23400 KB Correct.
63 Correct 83 ms 23528 KB Correct.
64 Correct 96 ms 21368 KB Correct.
65 Correct 75 ms 23396 KB Correct.
66 Correct 95 ms 23148 KB Correct.
67 Correct 101 ms 24172 KB Correct.
68 Correct 90 ms 24172 KB Correct.
69 Correct 74 ms 22988 KB Correct.
70 Correct 74 ms 23148 KB Correct.
71 Correct 107 ms 24812 KB Correct.
72 Correct 76 ms 24560 KB Correct.
73 Correct 97 ms 24936 KB Correct.
74 Correct 100 ms 24808 KB Correct.
75 Correct 98 ms 24936 KB Correct.