oj.uz

Submission #229154

# Submission time Handle Problem Language Result Execution time Memory
229154 2020-05-03T13:41:51 Z wleung_bvg Skandi (COCI20_skandi) C++17
50 / 110
 10000 ms 24168 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] && dfs(mate[w]))) { mate[mate[v] = w] = v; return true; }
        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 12416 KB Correct.
3 Correct 11 ms 12416 KB Correct.
4 Correct 12 ms 12288 KB Correct.
5 Correct 12 ms 12416 KB Correct.
6 Correct 13 ms 12416 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 11 ms 12416 KB Correct.
9 Correct 13 ms 12288 KB Correct.
10 Correct 12 ms 12416 KB Correct.
11 Correct 11 ms 12416 KB Correct.
12 Correct 11 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 12288 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 11 ms 12416 KB Correct.
21 Correct 11 ms 12288 KB Correct.
22 Correct 11 ms 12288 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 12288 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 12544 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 12 ms 12416 KB Correct.
9 Correct 12 ms 12544 KB Correct.
10 Correct 12 ms 12672 KB Correct.
11 Correct 12 ms 12672 KB Correct.
12 Correct 12 ms 12672 KB Correct.
13 Correct 13 ms 12672 KB Correct.
14 Correct 14 ms 12672 KB Correct.
15 Correct 12 ms 12672 KB Correct.
16 Correct 13 ms 12672 KB Correct.
17 Correct 12 ms 12672 KB Correct.
18 Correct 12 ms 12672 KB Correct.
19 Correct 13 ms 12672 KB Correct.
20 Correct 12 ms 12672 KB Correct.
21 Correct 13 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 13 ms 12672 KB Correct.
26 Correct 13 ms 12672 KB Correct.

Subtask #3
0.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 12 ms 12288 KB Correct.
5 Correct 12 ms 12416 KB Correct.
6 Correct 13 ms 12416 KB Correct.
7 Correct 11 ms 12416 KB Correct.
8 Correct 11 ms 12416 KB Correct.
9 Correct 13 ms 12288 KB Correct.
10 Correct 12 ms 12416 KB Correct.
11 Correct 11 ms 12416 KB Correct.
12 Correct 11 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 12288 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 11 ms 12416 KB Correct.
21 Correct 11 ms 12288 KB Correct.
22 Correct 11 ms 12288 KB Correct.
23 Correct 11 ms 12288 KB Correct.
24 Correct 11 ms 12288 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 12544 KB Correct.
30 Correct 11 ms 12416 KB Correct.
31 Correct 12 ms 12416 KB Correct.
32 Correct 12 ms 12544 KB Correct.
33 Correct 12 ms 12672 KB Correct.
34 Correct 12 ms 12672 KB Correct.
35 Correct 12 ms 12672 KB Correct.
36 Correct 13 ms 12672 KB Correct.
37 Correct 14 ms 12672 KB Correct.
38 Correct 12 ms 12672 KB Correct.
39 Correct 13 ms 12672 KB Correct.
40 Correct 12 ms 12672 KB Correct.
41 Correct 12 ms 12672 KB Correct.
42 Correct 13 ms 12672 KB Correct.
43 Correct 12 ms 12672 KB Correct.
44 Correct 13 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 13 ms 12672 KB Correct.
49 Correct 13 ms 12672 KB Correct.
50 Correct 70 ms 22884 KB Correct.
51 Correct 3043 ms 21376 KB Correct.
52 Correct 103 ms 24048 KB Correct.
53 Correct 68 ms 23176 KB Correct.
54 Correct 81 ms 22512 KB Correct.
55 Correct 78 ms 24168 KB Correct.
56 Correct 71 ms 23912 KB Correct.
57 Correct 73 ms 23780 KB Correct.
58 Execution timed out 10033 ms 20588 KB Time limit exceeded
59 Halted 0 ms 0 KB -