Submission #234171

#	Time	Username	Problem	Language	Result	Execution time	Memory
234171		doowey	Skandi (COCI20_skandi)	C++14	55 / 110	87 ms	23732 KiB

Main

#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];

bool cover[N][N];

vector<pii> edg;
bool chk[MAX];
vector<pii> T[MAX];
vector<int> R[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()));
      R[up[i][j]].push_back(li[i][j]);
      edg.push_back(mp(li[i][j],up[i][j]));
    }
  }
  karp();
  int sol = 0;
  for(int i = 1; i <= ln; i ++ ){
    if(use[i]==-1){
      for(auto x : T[i]){
        if(match[x.fi] != -1) {
          tr[x.fi]=true;  
          break;
        }
      }
    }
    else{
      sol ++ ;
    }
  }
  for(int i = 1; i <= rn ; i ++ ){
    if(match[i]==-1){
      for(auto x : R[i]){
        if(use[x] != -1) {
          tl[x] = true;
          break;
        }
      }
    }
  }
  for(auto x : edg){
    if(tl[x.fi] || tr[x.se]) continue;
    tl[x.fi]=true;
  }
  cout << sol << "\n";
  for(int i = 1; i <= ln; i ++ ){
    if(tl[i]){
      for(int t = rid[i].se; t <= m ;t ++ ){
        if(cf[rid[i].fi][t] == '1') break;
        cover[rid[i].fi][t]=true;
      }
      cout << rid[i].fi << " " << rid[i].se - 1 << " DESNO\n";
    }
  }
  for(int i = 1; i <= rn ; i ++ ){
    if(tr[i]){
      for(int t = did[i].fi; t <= n; t ++ ){
        if(cf[t][did[i].se] == '1') break;
        cover[t][did[i].se]=true;
      }
      cout << did[i].fi - 1 << " " << did[i].se << " DOLJE\n";
    }
  }
  for(int i = 1; i <= n; i ++ ){
    for(int j = 1; j <= m ; j ++ ){
      if(cf[i][j] == '0'){
        if(!cover[i][j]){
          assert(0);
          return 0;
        }
      }
    }
  }
  return 0;
}

Compilation message (stderr)

skandi.cpp: In function 'void karp()':
skandi.cpp:59:8: warning: unused variable 'ok' [-Wunused-variable]
   bool ok = true;
        ^~

• Subtask 1: 9 / 18
• Subtask 2: 16 / 32
• Subtask 3: 30 / 60