oj.uz

Submission #234163

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

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]){
      cout << rid[i].fi << " " << rid[i].se - 1 << " DESNO\n";
    }
  }
  for(int i = 1; i <= rn ; i ++ ){
    if(tr[i]){
      cout << did[i].fi - 1 << " " << did[i].se << " DOLJE\n";
    }
  }
  return 0;
}

Compilation message

skandi.cpp: In function 'void karp()':
skandi.cpp:57: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 11 ms 12672 KB Correct.
3 Correct 12 ms 12672 KB Correct.
4 Correct 12 ms 12672 KB Correct.
5 Correct 12 ms 12672 KB Correct.
6 Correct 14 ms 12648 KB Correct.
7 Partially correct 11 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 Correct 12 ms 12672 KB Correct.
11 Correct 12 ms 12672 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 14 ms 12672 KB Correct.
18 Correct 12 ms 12672 KB Correct.
19 Correct 12 ms 12672 KB Correct.
20 Correct 12 ms 12672 KB Correct.
21 Correct 12 ms 12672 KB Correct.
22 Correct 12 ms 12672 KB Correct.
23 Correct 12 ms 12672 KB Correct.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13952 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 14208 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 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 13 ms 13568 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 14 ms 14976 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 15 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 16 ms 14976 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 15 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 14 ms 15104 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 11 ms 12672 KB Correct.
3 Correct 12 ms 12672 KB Correct.
4 Correct 12 ms 12672 KB Correct.
5 Correct 12 ms 12672 KB Correct.
6 Correct 14 ms 12648 KB Correct.
7 Partially correct 11 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 Correct 12 ms 12672 KB Correct.
11 Correct 12 ms 12672 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 14 ms 12672 KB Correct.
18 Correct 12 ms 12672 KB Correct.
19 Correct 12 ms 12672 KB Correct.
20 Correct 12 ms 12672 KB Correct.
21 Correct 12 ms 12672 KB Correct.
22 Correct 12 ms 12672 KB Correct.
23 Correct 12 ms 12672 KB Correct.
24 Correct 12 ms 13952 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 14208 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 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 13 ms 13568 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 14 ms 14976 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 15 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 16 ms 14976 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 15 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 14 ms 15104 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 54 ms 21356 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 77 ms 20708 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 75 ms 23016 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 52 ms 21488 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 61 ms 21784 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 63 ms 22760 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 57 ms 21868 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 55 ms 21740 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 89 ms 20580 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 55 ms 21228 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 63 ms 22124 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 66 ms 21860 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 63 ms 21996 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 63 ms 22252 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 29 ms 19952 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 59 ms 22124 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 74 ms 22116 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 71 ms 23020 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 70 ms 22888 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 63 ms 21992 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 55 ms 21992 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 72 ms 23524 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 59 ms 22380 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 70 ms 23528 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 69 ms 23528 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 80 ms 23472 KB First line is correct, but the reconstruction is not properly formatted.