Submission #530981

#TimeUsernameProblemLanguageResultExecution timeMemory
530981Tenis0206Skandi (COCI20_skandi)C++11
110 / 110
180 ms14876 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...