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;
int n,m;
char c[505][505];
int sus[505][505], stg[505][505];
vector<int> G[250005];
bool sel[250005], st[250005], dr[250005];
int l[250005],r[250005];
bool cupleaza(int nod)
{
sel[nod] = true;
for(auto it : G[nod])
{
if(!r[it])
{
r[it] = nod;
l[nod] = it;
return true;
}
}
for(auto it : G[nod])
{
if(!sel[r[it]] && cupleaza(r[it]))
{
r[it] = nod;
l[nod] = it;
return true;
}
}
return false;
}
void dfs(int nod)
{
for(auto it : G[nod])
{
if(!dr[it])
{
dr[it] = true;
st[r[it]] = false;
dfs(r[it]);
}
}
}
pair<int,int> decod(int val)
{
int l = (val - 1) / m + 1;
int c = (val - 1) % m + 1;
return {l,c};
}
string output[2];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
output[0] = "DESNO";
output[1] = "DOLJE";
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c[i][j];
if(c[i][j]=='1')
{
sus[i][j] = (i - 1) * m + j;
stg[i][j] = (i - 1) * m + j;
}
else
{
sus[i][j] = sus[i-1][j];
stg[i][j] = stg[i][j-1];
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(c[i][j]=='1')
{
continue;
}
G[stg[i][j]].push_back(sus[i][j]);
}
}
bool done = false;
while(!done)
{
done = true;
memset(sel,0,sizeof(sel));
for(int i=1;i<=n*m;i++)
{
if(!l[i] && !sel[i] && cupleaza(i))
{
done = false;
}
}
}
for(int i=1;i<=n*m;i++)
{
if(l[i])
{
st[i] = true;
}
}
for(int i=1;i<=n*m;i++)
{
if(!l[i])
{
dfs(i);
}
}
vector<pair<pair<int,int>,int>> rez;
for(int i=1;i<=n*m;i++)
{
if(st[i])
{
rez.push_back({decod(i),0});
}
if(dr[i])
{
rez.push_back({decod(i),1});
}
}
cout<<rez.size()<<'\n';
for(auto it : rez)
{
cout<<it.first.first<<' '<<it.first.second<<' '<<output[it.second]<<'\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |