oj.uz

Submission #845374

# Submission time Handle Problem Language Result Execution time Memory
845374 2023-09-06T13:23:13 Z vjudge1 Skandi (COCI20_skandi) C++17
9 / 110
 14 ms 55468 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;
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;
  if(col){
    white.pb(v);
  }else{
    nigga.pb(v);
  }
  pair<int, int> dpv = {1, 0};
  for(int u: g[v]){
    if(!vis[u]){
      auto dpu = dfs(u, col^1);
      dpv.first = min(dpv.first + dpu.first, dpv.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]){
      pair<int, int> dpv = dfs(i, 0);
      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:102:15: warning: unused variable 'aa' [-Wunused-variable]
  102 |   int tt = 1, aa;
      |               ^~

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 12 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 12 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 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 12 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 11 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 12 ms 55388 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 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 11 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 12 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 11 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 11 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 11 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 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 12 ms 55388 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 12 ms 55468 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 12 ms 55384 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 11 ms 55256 KB First line is correct, but the reconstruction is not properly formatted.
7 Incorrect 12 ms 55384 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 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 12 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 12 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 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 12 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 11 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 12 ms 55388 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 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 11 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 11 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 12 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 11 ms 55128 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 11 ms 55132 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 11 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 12 ms 55384 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 12 ms 55388 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 12 ms 55468 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 12 ms 55384 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 11 ms 55256 KB First line is correct, but the reconstruction is not properly formatted.
30 Incorrect 12 ms 55384 KB First line is not correct.
31 Halted 0 ms 0 KB -