oj.uz

Submission #845410

# Submission time Handle Problem Language Result Execution time Memory
845410 2023-09-06T13:30:48 Z vjudge1 Skandi (COCI20_skandi) C++17
9 / 110
 15 ms 55640 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;
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;

pair<int, int> dfs(int v, bool col){
  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, col^1);
      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);

  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);
        }
        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, 0);
      if(tot == 1) ans++;
      else ans += min(dpv.first, dpv.second);
    }
  }
  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, bool)':
skandi.cpp:24: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]
   24 |   if(v <= n*m && v > segdown.size()) return {0, 0};
      |                  ~~^~~~~~~~~~~~~~~~
skandi.cpp:25: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]
   25 |   if(v > n*m && v > segright.size()+n*m) return {0, 0};
      |                 ~~^~~~~~~~~~~~~~~~~~~~~
skandi.cpp: In function 'int main()':
skandi.cpp:100:15: warning: unused variable 'aa' [-Wunused-variable]
  100 |   int tt = 1, aa;
      |               ^~

Subtask #1
9.0 / 18.0

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

Subtask #2
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 15 ms 55640 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 13 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 13 ms 55388 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 13 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
7 Incorrect 12 ms 55268 KB First line is not correct.
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 11 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 12 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 13 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 13 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 13 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 11 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 11 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 11 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 12 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 12 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 12 ms 55180 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 15 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 14 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 14 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 14 ms 55200 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 14 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 12 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 15 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 12 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 14 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 15 ms 55640 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 13 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 13 ms 55388 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 13 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
30 Incorrect 12 ms 55268 KB First line is not correct.
31 Halted 0 ms 0 KB -