oj.uz

Submission #845520

# Submission time Handle Problem Language Result Execution time Memory
845520 2023-09-06T13:59:40 Z vjudge1 Skandi (COCI20_skandi) C++17
55 / 110
 3092 ms 76028 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 18;



int n, m, tot = 0, white = 0, nigga = 0;
string s[N];
vector<int> g[N];
vector<pair<int, int>> segdown;
vector<pair<int, int>> segright;
vector<bool> vis(N);
// vector<int> white;
// vector<int> nigga;



vector<int> mt(N, -1);
vector<bool> used;

bool try_kuhn(int v) {
  if (used[v - 1])
    return false;
  used[v - 1] = true;
  for (int to : g[v]) {
    if (mt[to] == -1 || try_kuhn(mt[to])) {
      mt[to] = v;
      return true;
    }
  }
  return false;
}


pair<int, int> dfs(int v){
  if(v <= n*m && v > segdown.size()) return {0, 0};
  if(v > n*m && v > segright.size()+n*m) return {0, 0};

  vis[v] = 1;
  tot++;
  pair<int, int> dpv = {1, 0};
  for(int u: g[v]){
    if(!vis[u]){
      auto dpu = dfs(u);
      dpv.first += min(dpu.first, dpu.second);
      dpv.second += dpu.first;
    }
  }
  return dpv;
}

void solve(){
  cin >> n >> m;
  for(int i = 0; i < n; ++i) cin >> s[i];
  
  vector<vector<vector<int>>> c(n);
  for(int i = 0; i < n; ++i) c[i].resize(m);

  vector<int> kuhn;

  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(s[i][j] == '0' && s[i - 1][j] == '1'){
        int idx = segdown.size() + 1;
        for(int k = i; k < n; ++k){
          if(s[k][j] == '1') break;
          c[k][j].pb(idx);
        }
        kuhn.pb(idx);
        segdown.pb({i, j});
      }
      if(s[i][j] == '0' && s[i][j - 1] == '1'){
        int idx = n*m+segright.size()+1;
        for(int k = j; k < m; ++k){
          if(s[i][k] == '1') break;
          c[i][k].pb(idx);
        }
        segright.pb({i, j});
      }
    }
  }
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(s[i][j] == '0'){
        g[c[i][j][0]].pb(c[i][j][1]);
        g[c[i][j][1]].pb(c[i][j][0]);
      }
    }
  }
  int ans = 0;
  // for(int i = 1; i <= 2*n*m; ++i){
  //   if(!vis[i]){
  //     tot = 0;
  //     pair<int, int> dpv = dfs(i);
  //     if(tot == 1) ans++;
  //     else ans += min(dpv.first, dpv.second);
  //   }
  // }
  for(int v: kuhn){
    used.assign(segdown.size(), false);
    try_kuhn(v);
  }
  for (int i = 0; i < segright.size(); ++i)
    if (mt[i+n*m+1] != -1)
      ++ans;
  cout << ans;
  return;
  // if(white.size() > nigga.size()) white.swap(nigga);
  // cout << white.size() << '\n';
  // for(auto w: white){
  //   if(w >= n*m){
  //     cout << segright[w - n*m - 1].first + 1 << ' ' << segright[w - n*m - 1].second << ' '<< "DESNO\n";
  //   }else{
  //     cout << segdown[w - 1].first << ' ' << segdown[w - 1].second + 1 << ' '<< "DOLJE\n";
  //   }
  // }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // cin >> tt;
  while(tt--){
    solve();
    // en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

skandi.cpp: In function 'std::pair<int, int> dfs(int)':
skandi.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   if(v <= n*m && v > segdown.size()) return {0, 0};
      |                  ~~^~~~~~~~~~~~~~~~
skandi.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   if(v > n*m && v > segright.size()+n*m) return {0, 0};
      |                 ~~^~~~~~~~~~~~~~~~~~~~~
skandi.cpp: In function 'void solve()':
skandi.cpp:110:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for (int i = 0; i < segright.size(); ++i)
      |                   ~~^~~~~~~~~~~~~~~~~
skandi.cpp: In function 'int main()':
skandi.cpp:129:15: warning: unused variable 'aa' [-Wunused-variable]
  129 |   int tt = 1, aa;
      |               ^~

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 12 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 12 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 13 ms 59088 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 13 ms 59224 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 13 ms 59224 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 12 ms 59232 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 13 ms 59108 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 13 ms 59304 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 14 ms 59308 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 13 ms 59224 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 12 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 12 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 13 ms 59064 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 14 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 13 ms 59084 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 13 ms 59284 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 13 ms 59364 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 12 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 13 ms 59340 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 13 ms 59564 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 14 ms 59572 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 13 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 14 ms 59568 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 13 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 13 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 14 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 15 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 14 ms 59560 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 17 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 15 ms 59516 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 14 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 14 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 14 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 13 ms 59544 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 13 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 14 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 14 ms 59480 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 Partially correct 13 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 12 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 12 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 13 ms 59088 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 13 ms 59224 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 13 ms 59224 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 12 ms 59232 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 13 ms 59108 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 13 ms 59304 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 14 ms 59308 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 13 ms 59224 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 12 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 12 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 13 ms 59064 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 14 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 13 ms 59084 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 13 ms 59284 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 13 ms 59364 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 13 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 12 ms 59228 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 13 ms 59340 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 13 ms 59564 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 14 ms 59572 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 13 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 14 ms 59568 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 13 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 13 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 14 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 15 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 14 ms 59560 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 17 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 15 ms 59516 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 14 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 14 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 14 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 13 ms 59544 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 13 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 14 ms 59484 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 14 ms 59480 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 41 ms 71776 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 3092 ms 73344 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 56 ms 74944 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 40 ms 71624 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 49 ms 72860 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 48 ms 73744 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 47 ms 72568 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 41 ms 72552 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 1948 ms 74108 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 41 ms 71372 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 51 ms 72768 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 60 ms 73284 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 45 ms 73280 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 49 ms 72864 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 98 ms 73756 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 43 ms 72768 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 56 ms 74056 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 72 ms 75968 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 49 ms 74176 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 45 ms 72384 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 44 ms 72384 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 59 ms 75748 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 44 ms 73404 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 54 ms 75456 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 59 ms 76028 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 66 ms 75076 KB First line is correct, but the reconstruction is not properly formatted.