This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 510;
const int MAX = N * N;
char cf[N][N];
int li[N][N];
int up[N][N];
pii did[MAX];
pii rid[MAX];
int use[MAX];
int match[MAX];
bool vis[MAX];
int dis[MAX];
int sa[MAX], sb[MAX];
bool tl[MAX], tr[MAX];
vector<pii> edg;
bool chk[MAX];
vector<pii> T[MAX];
int ln, rn;
bool dfs(int u){
vis[u]=true;
for(auto x : T[u]){
if(match[x.fi] == -1 || (!vis[match[x.fi]] && dis[match[x.fi]] == dis[u] + 1 && dfs(match[x.fi]))){
match[x.fi]=u;
use[u]=x.se;
return true;
}
}
return false;
}
void karp(){
int cur = 0, f = 0;
for(int i = 1 ; i <= ln; i ++ ){
use[i]=-1;
}
for(int i = 1; i <= rn; i ++ ){
match[i]=-1;
}
bool ok = true;
while(1){
f = 0;
queue<int> bf;
for(int i = 1; i <= ln; i ++ ){
if(use[i] == -1){
bf.push(i);
dis[i]=0;
}
else{
dis[i]=-1;
}
}
int node;
while(!bf.empty()){
node=bf.front();
bf.pop();
for(auto x : T[node]){
if(match[x.fi] != -1 && dis[match[x.fi]] == -1){
dis[match[x.fi]] = dis[node] + 1;
bf.push(match[x.fi]);
}
}
}
for(int i = 1; i <= ln; i ++ ) vis[i]=false;
for(int i = 1; i <= ln ;i ++ ){
if(use[i] == -1){
f += dfs(i);
}
}
if(!f){
return;
}
cur += f;
}
}
int main(){
fastIO;
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= m ; j ++ ){
cin >> cf[i][j];
}
}
bool has;
for(int i = 1; i <= n; i ++ ){
has=false;
for(int j = 1; j <= m ; j ++ ){
if(cf[i][j] == '0'){
if(!has){
ln++;
rid[ln]=mp(i,j);
has=true;
}
li[i][j]=ln;
}
else{
has=false;
}
}
}
for(int i = 1; i <= m ; i ++ ){
has=false;
for(int j = 1; j <= n ; j ++ ){
if(cf[j][i] == '0'){
if(!has){
rn++;
did[rn]=mp(j,i);
has=true;
}
up[j][i]=rn;
}
else{
has=false;
}
}
}
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= m ; j ++ ){
if(cf[i][j]=='1') continue;
T[li[i][j]].push_back(mp(up[i][j], (int)edg.size()));
edg.push_back(mp(li[i][j],up[i][j]));
}
}
karp();
for(int i = 1; i <= ln; i ++) {
if(use[i] != -1){
chk[use[i]]=true;
}
}
for(int i = 0 ; i < edg.size(); i ++ ){
if(chk[i]) continue;
if(use[edg[i].fi] == -1) tr[edg[i].se] =true ;
if(match[edg[i].se] == -1) tl[edg[i].fi] =true ;
}
int sol = 0;
for(int i = 0 ; i < edg.size(); i ++ ){
if(chk[i]){
sol ++ ;
if(tl[edg[i].fi] || tr[edg[i].se]) continue;
else tl[edg[i].fi]=true;
}
}
cout << sol << "\n";
for(int i = 1; i <= ln; i ++ ){
if(tl[i]){
cout << rid[i].fi << " " << rid[i].se - 1 << " DESNO\n";
}
}
for(int i = 1; i <= rn ; i ++ ){
if(tr[i]){
cout << did[i].fi - 1 << " " << did[i].se << " DOLJE\n";
}
}
return 0;
}
Compilation message (stderr)
skandi.cpp: In function 'void karp()':
skandi.cpp:56:8: warning: unused variable 'ok' [-Wunused-variable]
bool ok = true;
^~
skandi.cpp: In function 'int main()':
skandi.cpp:148:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < edg.size(); i ++ ){
~~^~~~~~~~~~~~
skandi.cpp:154:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < edg.size(); i ++ ){
~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |