oj.uz

Submission #218282

# Submission time Handle Problem Language Result Execution time Memory
218282 2020-04-01T19:41:37 Z dolphingarlic Skandi (COCI20_skandi) C++14
110 / 110
 103 ms 23208 KB 
/*
COCI 2020 Skandi
- If we view horizontal and vertical words as nodes in a graph and connect words if they intersect,
  we get a bipartite graph
- The problem now becomes finding the minimum vertex cover of this graph
    - By Konig's theorem, this is equal to the maximum bipartite matching
    - We can use the Hopcraft-Karp algorithm for this
    - To construct the vertex cover, we do a DFS and magic happens
- Complexity: O(N^3)
*/

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
 
bool dfs(int a, int L, vector<vector<int>>& g, vector<int>& btoa, vector<int>& A, vector<int>& B) {
    if (A[a] != L) return 0;
    A[a] = -1;
    for (int b : g[a]) if (B[b] == L + 1) {
        B[b] = 0;
        if (btoa[b] == -1 || dfs(btoa[b], L + 1, g, btoa, A, B))
            return btoa[b] = a, 1;
    }
    return 0;
}
 
int hopcroftKarp(vector<vector<int>>& g, vector<int>& btoa) {
    int res = 0;
    vector<int> A(g.size()), B(btoa.size()), cur, next;
    for (;;) {
        fill(A.begin(), A.end(), 0);
        fill(B.begin(), B.end(), 0);
        /// Find the starting nodes for BFS (i.e. layer 0).
        cur.clear();
        for (int a : btoa) if(a != -1) A[a] = -1;
        FOR(a, 0, g.size()) if(A[a] == 0) cur.push_back(a);
        /// Find all layers using bfs.
        for (int lay = 1;; lay++) {
            bool islast = 0;
            next.clear();
            for (int a : cur) for (int b : g[a]) {
                if (btoa[b] == -1) {
                    B[b] = lay;
                    islast = 1;
                }
                else if (btoa[b] != a && !B[b]) {
                    B[b] = lay;
                    next.push_back(btoa[b]);
                }
            }
            if (islast) break;
            if (next.empty()) return res;
            for (int a : next) A[a] = lay;
            cur.swap(next);
        }
        /// Use DFS to scan for augmenting paths.
        FOR(a, 0, g.size())
            res += dfs(a, 0, g, btoa, A, B);
    }
}
 
char grid[501][501];
int c_horiz[501][501], c_vert[501][501], horiz = 0, vert = 0;
vector<pair<int, int>> horiz_loc, vert_loc;
bool visited[500001], has_edge[250001];
vector<int> graph[500001];
 
void fvc(int node) {
    visited[node] = true;
    for (int i : graph[node]) if (!visited[i]) fvc(i);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    FOR(i, 1, n + 1) FOR(j, 1, m + 1) {
        cin >> grid[i][j];
        if (grid[i][j] == '0') {
            if (grid[i][j - 1] == '1') {
                c_horiz[i][j] = horiz++;
                horiz_loc.push_back({i, j - 1});
            } else c_horiz[i][j] = c_horiz[i][j - 1];
 
            if (grid[i - 1][j] == '1') {
                c_vert[i][j] = vert++;
                vert_loc.push_back({i - 1, j});
            } else c_vert[i][j] = c_vert[i - 1][j];
        }
    }
 
    vector<vector<int>> g(vert);
    FOR(i, 1, n + 1) FOR(j, 1, m + 1) {
        if (grid[i][j] == '0') g[c_vert[i][j]].push_back(c_horiz[i][j]);
    }
 
    vector<int> btoa(horiz, -1);
    cout << hopcroftKarp(g, btoa) << '\n';
 
    FOR(i, 0, vert) for (int j : g[i]) {
        if (btoa[j] == i) {
            graph[vert + j].push_back(i);
            has_edge[i] = true;
        } else graph[i].push_back(vert + j);
    }
 
    FOR(i, 0, vert) if (!has_edge[i] && !visited[i]) fvc(i);
    FOR(i, 0, vert) if (!visited[i]) cout << vert_loc[i].first << ' ' << vert_loc[i].second << " DOLJE\n";
    FOR(i, 0, horiz) if (visited[vert + i]) cout << horiz_loc[i].first << ' ' << horiz_loc[i].second << " DESNO\n";
    return 0;
}

Compilation message

skandi.cpp: In function 'int hopcroftKarp(std::vector<std::vector<int> >&, std::vector<int>&)':
skandi.cpp:13:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
skandi.cpp:37:13:
         FOR(a, 0, g.size()) if(A[a] == 0) cur.push_back(a);
             ~~~~~~~~~~~~~~              
skandi.cpp:37:9: note: in expansion of macro 'FOR'
         FOR(a, 0, g.size()) if(A[a] == 0) cur.push_back(a);
         ^~~
skandi.cpp:13:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
skandi.cpp:58:13:
         FOR(a, 0, g.size())
             ~~~~~~~~~~~~~~              
skandi.cpp:58:9: note: in expansion of macro 'FOR'
         FOR(a, 0, g.size())
         ^~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Correct.
2 Correct 11 ms 12160 KB Correct.
3 Correct 11 ms 12160 KB Correct.
4 Correct 11 ms 12160 KB Correct.
5 Correct 11 ms 12160 KB Correct.
6 Correct 11 ms 12160 KB Correct.
7 Correct 11 ms 12160 KB Correct.
8 Correct 11 ms 12160 KB Correct.
9 Correct 13 ms 12288 KB Correct.
10 Correct 11 ms 12160 KB Correct.
11 Correct 12 ms 12160 KB Correct.
12 Correct 11 ms 12160 KB Correct.
13 Correct 11 ms 12160 KB Correct.
14 Correct 11 ms 12160 KB Correct.
15 Correct 11 ms 12160 KB Correct.
16 Correct 12 ms 12160 KB Correct.
17 Correct 11 ms 12160 KB Correct.
18 Correct 11 ms 12160 KB Correct.
19 Correct 12 ms 12160 KB Correct.
20 Correct 14 ms 12160 KB Correct.
21 Correct 14 ms 12160 KB Correct.
22 Correct 11 ms 12160 KB Correct.
23 Correct 11 ms 12160 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13312 KB Correct.
2 Correct 12 ms 12928 KB Correct.
3 Correct 12 ms 13696 KB Correct.
4 Correct 12 ms 12800 KB Correct.
5 Correct 12 ms 12800 KB Correct.
6 Correct 11 ms 12544 KB Correct.
7 Correct 12 ms 12416 KB Correct.
8 Correct 12 ms 12928 KB Correct.
9 Correct 13 ms 14464 KB Correct.
10 Correct 14 ms 14464 KB Correct.
11 Correct 15 ms 14464 KB Correct.
12 Correct 14 ms 14464 KB Correct.
13 Correct 13 ms 14464 KB Correct.
14 Correct 13 ms 14464 KB Correct.
15 Correct 13 ms 14464 KB Correct.
16 Correct 13 ms 14464 KB Correct.
17 Correct 13 ms 14464 KB Correct.
18 Correct 13 ms 14464 KB Correct.
19 Correct 13 ms 14464 KB Correct.
20 Correct 13 ms 14464 KB Correct.
21 Correct 13 ms 14464 KB Correct.
22 Correct 13 ms 14464 KB Correct.
23 Correct 13 ms 14464 KB Correct.
24 Correct 13 ms 14464 KB Correct.
25 Correct 14 ms 14464 KB Correct.
26 Correct 14 ms 14464 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Correct.
2 Correct 11 ms 12160 KB Correct.
3 Correct 11 ms 12160 KB Correct.
4 Correct 11 ms 12160 KB Correct.
5 Correct 11 ms 12160 KB Correct.
6 Correct 11 ms 12160 KB Correct.
7 Correct 11 ms 12160 KB Correct.
8 Correct 11 ms 12160 KB Correct.
9 Correct 13 ms 12288 KB Correct.
10 Correct 11 ms 12160 KB Correct.
11 Correct 12 ms 12160 KB Correct.
12 Correct 11 ms 12160 KB Correct.
13 Correct 11 ms 12160 KB Correct.
14 Correct 11 ms 12160 KB Correct.
15 Correct 11 ms 12160 KB Correct.
16 Correct 12 ms 12160 KB Correct.
17 Correct 11 ms 12160 KB Correct.
18 Correct 11 ms 12160 KB Correct.
19 Correct 12 ms 12160 KB Correct.
20 Correct 14 ms 12160 KB Correct.
21 Correct 14 ms 12160 KB Correct.
22 Correct 11 ms 12160 KB Correct.
23 Correct 11 ms 12160 KB Correct.
24 Correct 12 ms 13312 KB Correct.
25 Correct 12 ms 12928 KB Correct.
26 Correct 12 ms 13696 KB Correct.
27 Correct 12 ms 12800 KB Correct.
28 Correct 12 ms 12800 KB Correct.
29 Correct 11 ms 12544 KB Correct.
30 Correct 12 ms 12416 KB Correct.
31 Correct 12 ms 12928 KB Correct.
32 Correct 13 ms 14464 KB Correct.
33 Correct 14 ms 14464 KB Correct.
34 Correct 15 ms 14464 KB Correct.
35 Correct 14 ms 14464 KB Correct.
36 Correct 13 ms 14464 KB Correct.
37 Correct 13 ms 14464 KB Correct.
38 Correct 13 ms 14464 KB Correct.
39 Correct 13 ms 14464 KB Correct.
40 Correct 13 ms 14464 KB Correct.
41 Correct 13 ms 14464 KB Correct.
42 Correct 13 ms 14464 KB Correct.
43 Correct 13 ms 14464 KB Correct.
44 Correct 13 ms 14464 KB Correct.
45 Correct 13 ms 14464 KB Correct.
46 Correct 13 ms 14464 KB Correct.
47 Correct 13 ms 14464 KB Correct.
48 Correct 14 ms 14464 KB Correct.
49 Correct 14 ms 14464 KB Correct.
50 Correct 53 ms 21304 KB Correct.
51 Correct 103 ms 18440 KB Correct.
52 Correct 76 ms 22276 KB Correct.
53 Correct 54 ms 21384 KB Correct.
54 Correct 67 ms 20920 KB Correct.
55 Correct 65 ms 22580 KB Correct.
56 Correct 55 ms 21752 KB Correct.
57 Correct 56 ms 21612 KB Correct.
58 Correct 83 ms 17848 KB Correct.
59 Correct 54 ms 20992 KB Correct.
60 Correct 62 ms 21904 KB Correct.
61 Correct 74 ms 20560 KB Correct.
62 Correct 61 ms 21856 KB Correct.
63 Correct 60 ms 22112 KB Correct.
64 Correct 24 ms 16768 KB Correct.
65 Correct 58 ms 21984 KB Correct.
66 Correct 74 ms 21052 KB Correct.
67 Correct 85 ms 21692 KB Correct.
68 Correct 67 ms 22712 KB Correct.
69 Correct 61 ms 21736 KB Correct.
70 Correct 58 ms 21876 KB Correct.
71 Correct 83 ms 22752 KB Correct.
72 Correct 57 ms 22324 KB Correct.
73 Correct 79 ms 23208 KB Correct.
74 Correct 80 ms 22644 KB Correct.
75 Correct 78 ms 23188 KB Correct.