답안 #845520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
845520	2023-09-06T13:59:40 Z	vjudge1	Skandi (COCI20_skandi)	C++17	55 / 110	3092 ms	76028 KB

skandi

/* 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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.

답안 #845520

Compilation message

Subtask #1 9.0 / 18.0

Subtask #2 16.0 / 32.0

Subtask #3 30.0 / 60.0

Subtask #1
9.0 / 18.0

Subtask #2
16.0 / 32.0

Subtask #3
30.0 / 60.0