제출 #570650

#제출 시각아이디문제언어결과실행 시간메모리
570650NekoRollySkandi (COCI20_skandi)C++17
55 / 110
76 ms21212 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e2+4; const int inf = 1e9; int n,m,n1,n2,ans; vector<int> adj[N*N],_adj[N*N]; int L[N][N],U[N][N]; int _u[N*N],_v[N*N],dis[N*N]; pair<int,int> posU[N*N],posL[N*N]; char lab[N][N]; queue<int> d; bool vis[N*N]; bool bfs(){ for (int i=1; i<=n1; i++){ if (!_u[i]){ dis[i] = 0; d.push(i);} else dis[i] = inf; } dis[0] = inf; for (int u; d.size(); d.pop()){ u = d.front(); for (int v : adj[u]) if (dis[_v[v]] == inf){ dis[_v[v]] = dis[u] + 1; d.push(_v[v]); } } return dis[0] != inf; } bool dfs(int u){ if (!u) return 1; for (int v : adj[u]) if (dis[_v[v]] == dis[u]+1 && dfs(_v[v])){ _v[v] = u, _u[u] = v; return 1; } dis[u] = inf; return 0; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i=0; i<n; i++) for (int j=0; j<m; j++){ cin >> lab[i][j]; if (lab[i][j] == '0'){ if (lab[i-1][j] == '0') U[i][j] = U[i-1][j]; else U[i][j] = ++n1, posU[n1] = {i, j}; if (lab[i][j-1] == '0') L[i][j] = L[i][j-1]; else L[i][j] = ++n2, posL[n2] = {i, j}; adj[U[i][j]].push_back(L[i][j]); _adj[L[i][j]].push_back(U[i][j]); } } while (bfs()) for (int i=1; i<=n1; i++) if (!_u[i] && dfs(i)) ans++; cout << ans << "\n"; for (int i=1; i<=n1; i++) if (_u[i] && i == _v[_u[i]]) for (int v : adj[i]) if (!_v[v]){ cout << posU[i].first << " " << posU[i].second+1 << " DOLJE\n"; vis[_u[i]] = 1; break; } for (int i=1; i<=n2; i++) if (_v[i] && i == _u[_v[i]] && !vis[i]) cout << posL[i].first+1 << " " << posL[i].second << " DESNO\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...