Submission #229152

#TimeUsernameProblemLanguageResultExecution timeMemory
229152wleung_bvgSkandi (COCI20_skandi)C++17
110 / 110
290 ms25192 KiB
#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 { const int NONE = MAXV; 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() { lvl[NONE] = -1; int front = 0, back = 0; for (int v : type[0]) { if (mate[v] == NONE) 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] != NONE) q[back++] = mate[w]; } } return lvl[NONE] != -1; } bool dfs(int v) { for (int w : adj[v]) if (lvl[mate[w]] == lvl[v] + 1 && (mate[w] == NONE || 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] = NONE; } while (bfs()) for (int v : type[0]) if (mate[v] == NONE && 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] == NONE) 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...