oj.uz

Submission #234242

# Submission time Handle Problem Language Result Execution time Memory
234242 2020-05-23T14:07:29 Z doowey Skandi (COCI20_skandi) C++14
110 / 110
 76 ms 15720 KB 
#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];
bool tl[MAX], tr[MAX];

bool cover[N][N];

vector<pii> edg;
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;
  }
}

void fin(int x){
  tl[x]=false;
  for(auto p : T[x]){
    if(tr[p.fi]) continue;
    tr[p.fi]=true;
    fin(match[p.fi]);
  }
}

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();
  int sol = 0;
  for(int i = 1; i <= ln; i ++ ){
    if(use[i] != -1) {
      sol ++ ;
    }
    tl[i]=true;
  }
  for(int i = 1; i <= ln ; i ++ ){
    if(use[i] == -1){
      fin(i);
    }
  }
  cout << sol << "\n";
  int cnt = 0;
  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;
      }
      cnt ++ ;
      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;
      }
      cnt ++ ;
      cout << did[i].fi - 1 << " " << did[i].se << " DOLJE\n";
    }
  }
  assert(cnt == sol);
  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

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6528 KB Correct.
2 Correct 8 ms 6528 KB Correct.
3 Correct 8 ms 6528 KB Correct.
4 Correct 8 ms 6528 KB Correct.
5 Correct 8 ms 6528 KB Correct.
6 Correct 8 ms 6528 KB Correct.
7 Correct 8 ms 6528 KB Correct.
8 Correct 8 ms 6528 KB Correct.
9 Correct 8 ms 6528 KB Correct.
10 Correct 8 ms 6528 KB Correct.
11 Correct 8 ms 6528 KB Correct.
12 Correct 9 ms 6528 KB Correct.
13 Correct 8 ms 6528 KB Correct.
14 Correct 8 ms 6528 KB Correct.
15 Correct 8 ms 6528 KB Correct.
16 Correct 8 ms 6528 KB Correct.
17 Correct 8 ms 6528 KB Correct.
18 Correct 8 ms 6528 KB Correct.
19 Correct 8 ms 6528 KB Correct.
20 Correct 9 ms 6528 KB Correct.
21 Correct 9 ms 6528 KB Correct.
22 Correct 8 ms 6528 KB Correct.
23 Correct 8 ms 6528 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8064 KB Correct.
2 Correct 10 ms 7552 KB Correct.
3 Correct 9 ms 8320 KB Correct.
4 Correct 9 ms 7424 KB Correct.
5 Correct 9 ms 7296 KB Correct.
6 Correct 9 ms 6912 KB Correct.
7 Correct 8 ms 6912 KB Correct.
8 Correct 9 ms 7424 KB Correct.
9 Correct 10 ms 9088 KB Correct.
10 Correct 10 ms 9088 KB Correct.
11 Correct 10 ms 9088 KB Correct.
12 Correct 11 ms 9088 KB Correct.
13 Correct 10 ms 9088 KB Correct.
14 Correct 10 ms 9088 KB Correct.
15 Correct 10 ms 9216 KB Correct.
16 Correct 10 ms 9088 KB Correct.
17 Correct 10 ms 9088 KB Correct.
18 Correct 10 ms 9088 KB Correct.
19 Correct 10 ms 9216 KB Correct.
20 Correct 10 ms 9216 KB Correct.
21 Correct 10 ms 9216 KB Correct.
22 Correct 10 ms 9088 KB Correct.
23 Correct 10 ms 9088 KB Correct.
24 Correct 10 ms 9088 KB Correct.
25 Correct 11 ms 9088 KB Correct.
26 Correct 11 ms 9216 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6528 KB Correct.
2 Correct 8 ms 6528 KB Correct.
3 Correct 8 ms 6528 KB Correct.
4 Correct 8 ms 6528 KB Correct.
5 Correct 8 ms 6528 KB Correct.
6 Correct 8 ms 6528 KB Correct.
7 Correct 8 ms 6528 KB Correct.
8 Correct 8 ms 6528 KB Correct.
9 Correct 8 ms 6528 KB Correct.
10 Correct 8 ms 6528 KB Correct.
11 Correct 8 ms 6528 KB Correct.
12 Correct 9 ms 6528 KB Correct.
13 Correct 8 ms 6528 KB Correct.
14 Correct 8 ms 6528 KB Correct.
15 Correct 8 ms 6528 KB Correct.
16 Correct 8 ms 6528 KB Correct.
17 Correct 8 ms 6528 KB Correct.
18 Correct 8 ms 6528 KB Correct.
19 Correct 8 ms 6528 KB Correct.
20 Correct 9 ms 6528 KB Correct.
21 Correct 9 ms 6528 KB Correct.
22 Correct 8 ms 6528 KB Correct.
23 Correct 8 ms 6528 KB Correct.
24 Correct 9 ms 8064 KB Correct.
25 Correct 10 ms 7552 KB Correct.
26 Correct 9 ms 8320 KB Correct.
27 Correct 9 ms 7424 KB Correct.
28 Correct 9 ms 7296 KB Correct.
29 Correct 9 ms 6912 KB Correct.
30 Correct 8 ms 6912 KB Correct.
31 Correct 9 ms 7424 KB Correct.
32 Correct 10 ms 9088 KB Correct.
33 Correct 10 ms 9088 KB Correct.
34 Correct 10 ms 9088 KB Correct.
35 Correct 11 ms 9088 KB Correct.
36 Correct 10 ms 9088 KB Correct.
37 Correct 10 ms 9088 KB Correct.
38 Correct 10 ms 9216 KB Correct.
39 Correct 10 ms 9088 KB Correct.
40 Correct 10 ms 9088 KB Correct.
41 Correct 10 ms 9088 KB Correct.
42 Correct 10 ms 9216 KB Correct.
43 Correct 10 ms 9216 KB Correct.
44 Correct 10 ms 9216 KB Correct.
45 Correct 10 ms 9088 KB Correct.
46 Correct 10 ms 9088 KB Correct.
47 Correct 10 ms 9088 KB Correct.
48 Correct 11 ms 9088 KB Correct.
49 Correct 11 ms 9216 KB Correct.
50 Correct 38 ms 13944 KB Correct.
51 Correct 59 ms 13412 KB Correct.
52 Correct 51 ms 15336 KB Correct.
53 Correct 37 ms 14060 KB Correct.
54 Correct 42 ms 14192 KB Correct.
55 Correct 44 ms 14956 KB Correct.
56 Correct 39 ms 14316 KB Correct.
57 Correct 38 ms 14184 KB Correct.
58 Correct 76 ms 13540 KB Correct.
59 Correct 39 ms 13932 KB Correct.
60 Correct 42 ms 14572 KB Correct.
61 Correct 45 ms 14440 KB Correct.
62 Correct 42 ms 14440 KB Correct.
63 Correct 43 ms 14696 KB Correct.
64 Correct 25 ms 13296 KB Correct.
65 Correct 42 ms 14572 KB Correct.
66 Correct 47 ms 14568 KB Correct.
67 Correct 49 ms 15464 KB Correct.
68 Correct 47 ms 15348 KB Correct.
69 Correct 39 ms 14444 KB Correct.
70 Correct 41 ms 14444 KB Correct.
71 Correct 52 ms 15716 KB Correct.
72 Correct 42 ms 14704 KB Correct.
73 Correct 55 ms 15720 KB Correct.
74 Correct 51 ms 15716 KB Correct.
75 Correct 50 ms 15592 KB Correct.