oj.uz

Submission #234171

# Submission time Handle Problem Language Result Execution time Memory
234171 2020-05-23T12:52:47 Z doowey Skandi (COCI20_skandi) C++14
55 / 110
 87 ms 23732 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];
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

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

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12672 KB Correct.
2 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
3 Correct 12 ms 12672 KB Correct.
4 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
5 Correct 12 ms 12672 KB Correct.
6 Correct 12 ms 12672 KB Correct.
7 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
9 Correct 12 ms 12672 KB Correct.
10 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
11 Correct 12 ms 12672 KB Correct.
12 Partially correct 11 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
13 Correct 11 ms 12672 KB Correct.
14 Correct 12 ms 12672 KB Correct.
15 Correct 12 ms 12672 KB Correct.
16 Correct 12 ms 12672 KB Correct.
17 Correct 12 ms 12672 KB Correct.
18 Correct 12 ms 12672 KB Correct.
19 Correct 11 ms 12544 KB Correct.
20 Correct 11 ms 12672 KB Correct.
21 Correct 12 ms 12672 KB Correct.
22 Correct 13 ms 12672 KB Correct.
23 Correct 11 ms 12672 KB Correct.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14080 KB Correct.
2 Partially correct 15 ms 13696 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 14 ms 14464 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 12 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 12 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 13 ms 13056 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 12 ms 13056 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 12 ms 13568 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 13 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 14 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 14 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 14 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12672 KB Correct.
2 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
3 Correct 12 ms 12672 KB Correct.
4 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
5 Correct 12 ms 12672 KB Correct.
6 Correct 12 ms 12672 KB Correct.
7 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
9 Correct 12 ms 12672 KB Correct.
10 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
11 Correct 12 ms 12672 KB Correct.
12 Partially correct 11 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
13 Correct 11 ms 12672 KB Correct.
14 Correct 12 ms 12672 KB Correct.
15 Correct 12 ms 12672 KB Correct.
16 Correct 12 ms 12672 KB Correct.
17 Correct 12 ms 12672 KB Correct.
18 Correct 12 ms 12672 KB Correct.
19 Correct 11 ms 12544 KB Correct.
20 Correct 11 ms 12672 KB Correct.
21 Correct 12 ms 12672 KB Correct.
22 Correct 13 ms 12672 KB Correct.
23 Correct 11 ms 12672 KB Correct.
24 Correct 12 ms 14080 KB Correct.
25 Partially correct 15 ms 13696 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 14 ms 14464 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 12 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 12 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 13 ms 13056 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 12 ms 13056 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 12 ms 13568 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 13 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 14 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 14 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 14 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 14 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 55 ms 21484 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 76 ms 20708 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 71 ms 23140 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 52 ms 21612 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 60 ms 21864 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 66 ms 22764 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 55 ms 21996 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 55 ms 21868 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 87 ms 20708 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 55 ms 21352 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 62 ms 22248 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 62 ms 21988 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 61 ms 22124 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 66 ms 22404 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 30 ms 20080 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 61 ms 22252 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 68 ms 22248 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 73 ms 23140 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 69 ms 23256 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 60 ms 22124 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 59 ms 22124 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 80 ms 23732 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 57 ms 22508 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 75 ms 23652 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 72 ms 23652 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 71 ms 23524 KB First line is correct, but the reconstruction is not properly formatted.