oj.uz

답안 #229153

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229153 2020-05-03T13:39:11 Z wleung_bvg Skandi (COCI20_skandi) C++17
50 / 110
 10000 ms 22892 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;
        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) return true;
                if (lvl[mate[w]] == -1) lvl[q[back++] = mate[w]] = lvl[v] + 1;
            }
        }
        return false;
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12288 KB Correct.
2 Correct 11 ms 12416 KB Correct.
3 Correct 12 ms 12416 KB Correct.
4 Correct 11 ms 12416 KB Correct.
5 Correct 14 ms 12416 KB Correct.
6 Correct 11 ms 12288 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 11 ms 12288 KB Correct.
11 Correct 11 ms 12416 KB Correct.
12 Correct 12 ms 12416 KB Correct.
13 Correct 12 ms 12416 KB Correct.
14 Correct 12 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 11 ms 12288 KB Correct.
19 Correct 11 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 12416 KB Correct.

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12416 KB Correct.
2 Correct 11 ms 12416 KB Correct.
3 Correct 13 ms 12672 KB Correct.
4 Correct 11 ms 12448 KB Correct.
5 Correct 12 ms 12416 KB Correct.
6 Correct 12 ms 12416 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 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 12 ms 12672 KB Correct.
15 Correct 14 ms 12672 KB Correct.
16 Correct 12 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 13 ms 12672 KB Correct.
24 Correct 13 ms 12672 KB Correct.
25 Correct 12 ms 12672 KB Correct.
26 Correct 12 ms 12672 KB Correct.

Subtask #3
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12288 KB Correct.
2 Correct 11 ms 12416 KB Correct.
3 Correct 12 ms 12416 KB Correct.
4 Correct 11 ms 12416 KB Correct.
5 Correct 14 ms 12416 KB Correct.
6 Correct 11 ms 12288 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 11 ms 12288 KB Correct.
11 Correct 11 ms 12416 KB Correct.
12 Correct 12 ms 12416 KB Correct.
13 Correct 12 ms 12416 KB Correct.
14 Correct 12 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 11 ms 12288 KB Correct.
19 Correct 11 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 12416 KB Correct.
24 Correct 12 ms 12416 KB Correct.
25 Correct 11 ms 12416 KB Correct.
26 Correct 13 ms 12672 KB Correct.
27 Correct 11 ms 12448 KB Correct.
28 Correct 12 ms 12416 KB Correct.
29 Correct 12 ms 12416 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 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 12 ms 12672 KB Correct.
38 Correct 14 ms 12672 KB Correct.
39 Correct 12 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 13 ms 12672 KB Correct.
47 Correct 13 ms 12672 KB Correct.
48 Correct 12 ms 12672 KB Correct.
49 Correct 12 ms 12672 KB Correct.
50 Correct 79 ms 22892 KB Correct.
51 Execution timed out 10043 ms 20468 KB Time limit exceeded
52 Halted 0 ms 0 KB -