oj.uz

Submission #234169

# Submission time Handle Problem Language Result Execution time Memory
234169 2020-05-23T12:49:34 Z doowey Skandi (COCI20_skandi) C++14
55 / 110
 86 ms 23900 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;
      }
    }
    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;
      }
    }
  }
  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 Correct 14 ms 12672 KB Correct.
3 Correct 14 ms 12672 KB Correct.
4 Correct 12 ms 12672 KB Correct.
5 Correct 12 ms 12672 KB Correct.
6 Correct 13 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 12544 KB Correct.
10 Correct 12 ms 12672 KB Correct.
11 Correct 12 ms 12704 KB Correct.
12 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
13 Correct 12 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 12 ms 12672 KB Correct.
20 Correct 11 ms 12672 KB Correct.
21 Correct 11 ms 12672 KB Correct.
22 Correct 12 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 14 ms 14080 KB Correct.
2 Partially correct 12 ms 13568 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 13 ms 14464 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 13 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 13 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 12 ms 13056 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 13 ms 13056 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 14 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 15 ms 15280 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 15 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 15 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 14 ms 15408 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 14 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 15 ms 15360 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 15 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 15360 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 Correct 14 ms 12672 KB Correct.
3 Correct 14 ms 12672 KB Correct.
4 Correct 12 ms 12672 KB Correct.
5 Correct 12 ms 12672 KB Correct.
6 Correct 13 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 12544 KB Correct.
10 Correct 12 ms 12672 KB Correct.
11 Correct 12 ms 12704 KB Correct.
12 Partially correct 12 ms 12672 KB First line is correct, but the reconstruction is not properly formatted.
13 Correct 12 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 12 ms 12672 KB Correct.
20 Correct 11 ms 12672 KB Correct.
21 Correct 11 ms 12672 KB Correct.
22 Correct 12 ms 12672 KB Correct.
23 Correct 11 ms 12672 KB Correct.
24 Correct 14 ms 14080 KB Correct.
25 Partially correct 12 ms 13568 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 13 ms 14464 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 13 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 13 ms 13440 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 12 ms 13056 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 13 ms 13056 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 14 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 15 ms 15280 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 15 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 15 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 14 ms 15408 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 14 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 15 ms 15360 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 15 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 15360 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 54 ms 21740 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 80 ms 20836 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 72 ms 23396 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 54 ms 21864 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 64 ms 21992 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 63 ms 23020 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 57 ms 22256 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 58 ms 22100 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 85 ms 20836 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 58 ms 21612 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 63 ms 22380 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 81 ms 22244 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 63 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 59 ms 22508 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 29 ms 20336 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 64 ms 22508 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 71 ms 22372 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 72 ms 23396 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 66 ms 23276 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 61 ms 22252 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 64 ms 22252 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 79 ms 23884 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 65 ms 22764 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 86 ms 23900 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 73 ms 23780 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 76 ms 23780 KB First line is correct, but the reconstruction is not properly formatted.