oj.uz

Submission #848707

# Submission time Handle Problem Language Result Execution time Memory
848707 2023-09-13T10:11:58 Z mychecksedad Skandi (COCI20_skandi) C++17
110 / 110
 3010 ms 110144 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, M = 1e5+10, K = 18;



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

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;
}


void dfs(int v){
  vis[v] = 1;
  for(int u: g[v]){
    if(vis[u]) continue;
    if(orient[{u, v}]){
      if(u > v)
        dfs(u);
    }else{
      if(u < v)
        dfs(u);
    }
  }
}


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);
  }
  vector<bool> incident(N);
  for (int i = 0; i < segright.size(); ++i)
    if (mt[i+n*m+1] != -1){
      ++ans;
      orient[{mt[i + n*m + 1], i + n*m+1}] = 1;
      orient[{i + n*m + 1, mt[i + n*m + 1]}] = 1;
      incident[i + n*m + 1] = 1;
    }
  cout << ans << '\n';
  for(int i = n * m + 1; i <= 2*n*m; ++i)
    if(!vis[i] && !incident[i])
      dfs(i);
  vector<int> white;
  for(int i = 1; i <= n*m; ++i) if(vis[i]) white.pb(i);
  for(int i = n*m+1; i <= n*m*2; ++i) if(!vis[i]) white.pb(i);
  // cout << white.size() << '\n';
  for(auto w: white){
    if(w >= n*m + 1){
      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 'void solve()':
skandi.cpp:108: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]
  108 |   for (int i = 0; i < segright.size(); ++i)
      |                   ~~^~~~~~~~~~~~~~~~~
skandi.cpp: In function 'int main()':
skandi.cpp:135:15: warning: unused variable 'aa' [-Wunused-variable]
  135 |   int tt = 1, aa;
      |               ^~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 82780 KB Correct.
2 Correct 17 ms 82780 KB Correct.
3 Correct 18 ms 82780 KB Correct.
4 Correct 17 ms 82776 KB Correct.
5 Correct 17 ms 82888 KB Correct.
6 Correct 18 ms 82776 KB Correct.
7 Correct 19 ms 82780 KB Correct.
8 Correct 18 ms 82780 KB Correct.
9 Correct 17 ms 82780 KB Correct.
10 Correct 18 ms 82780 KB Correct.
11 Correct 18 ms 82780 KB Correct.
12 Correct 17 ms 82780 KB Correct.
13 Correct 18 ms 82780 KB Correct.
14 Correct 17 ms 82728 KB Correct.
15 Correct 19 ms 82776 KB Correct.
16 Correct 19 ms 82780 KB Correct.
17 Correct 17 ms 82788 KB Correct.
18 Correct 17 ms 82780 KB Correct.
19 Correct 19 ms 82780 KB Correct.
20 Correct 17 ms 82780 KB Correct.
21 Correct 17 ms 82780 KB Correct.
22 Correct 17 ms 82780 KB Correct.
23 Correct 17 ms 82848 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 82792 KB Correct.
2 Correct 17 ms 82780 KB Correct.
3 Correct 18 ms 83032 KB Correct.
4 Correct 17 ms 82776 KB Correct.
5 Correct 18 ms 82780 KB Correct.
6 Correct 17 ms 82776 KB Correct.
7 Correct 20 ms 82772 KB Correct.
8 Correct 18 ms 83036 KB Correct.
9 Correct 19 ms 83548 KB Correct.
10 Correct 18 ms 83288 KB Correct.
11 Correct 18 ms 83352 KB Correct.
12 Correct 19 ms 83288 KB Correct.
13 Correct 19 ms 83308 KB Correct.
14 Correct 18 ms 83432 KB Correct.
15 Correct 19 ms 83292 KB Correct.
16 Correct 18 ms 83292 KB Correct.
17 Correct 20 ms 83292 KB Correct.
18 Correct 18 ms 83340 KB Correct.
19 Correct 18 ms 83364 KB Correct.
20 Correct 19 ms 83288 KB Correct.
21 Correct 19 ms 83540 KB Correct.
22 Correct 19 ms 83292 KB Correct.
23 Correct 18 ms 83292 KB Correct.
24 Correct 18 ms 83292 KB Correct.
25 Correct 19 ms 83292 KB Correct.
26 Correct 19 ms 83292 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 82780 KB Correct.
2 Correct 17 ms 82780 KB Correct.
3 Correct 18 ms 82780 KB Correct.
4 Correct 17 ms 82776 KB Correct.
5 Correct 17 ms 82888 KB Correct.
6 Correct 18 ms 82776 KB Correct.
7 Correct 19 ms 82780 KB Correct.
8 Correct 18 ms 82780 KB Correct.
9 Correct 17 ms 82780 KB Correct.
10 Correct 18 ms 82780 KB Correct.
11 Correct 18 ms 82780 KB Correct.
12 Correct 17 ms 82780 KB Correct.
13 Correct 18 ms 82780 KB Correct.
14 Correct 17 ms 82728 KB Correct.
15 Correct 19 ms 82776 KB Correct.
16 Correct 19 ms 82780 KB Correct.
17 Correct 17 ms 82788 KB Correct.
18 Correct 17 ms 82780 KB Correct.
19 Correct 19 ms 82780 KB Correct.
20 Correct 17 ms 82780 KB Correct.
21 Correct 17 ms 82780 KB Correct.
22 Correct 17 ms 82780 KB Correct.
23 Correct 17 ms 82848 KB Correct.
24 Correct 17 ms 82792 KB Correct.
25 Correct 17 ms 82780 KB Correct.
26 Correct 18 ms 83032 KB Correct.
27 Correct 17 ms 82776 KB Correct.
28 Correct 18 ms 82780 KB Correct.
29 Correct 17 ms 82776 KB Correct.
30 Correct 20 ms 82772 KB Correct.
31 Correct 18 ms 83036 KB Correct.
32 Correct 19 ms 83548 KB Correct.
33 Correct 18 ms 83288 KB Correct.
34 Correct 18 ms 83352 KB Correct.
35 Correct 19 ms 83288 KB Correct.
36 Correct 19 ms 83308 KB Correct.
37 Correct 18 ms 83432 KB Correct.
38 Correct 19 ms 83292 KB Correct.
39 Correct 18 ms 83292 KB Correct.
40 Correct 20 ms 83292 KB Correct.
41 Correct 18 ms 83340 KB Correct.
42 Correct 18 ms 83364 KB Correct.
43 Correct 19 ms 83288 KB Correct.
44 Correct 19 ms 83540 KB Correct.
45 Correct 19 ms 83292 KB Correct.
46 Correct 18 ms 83292 KB Correct.
47 Correct 18 ms 83292 KB Correct.
48 Correct 19 ms 83292 KB Correct.
49 Correct 19 ms 83292 KB Correct.
50 Correct 71 ms 102952 KB Correct.
51 Correct 3010 ms 101104 KB Correct.
52 Correct 102 ms 108520 KB Correct.
53 Correct 71 ms 102896 KB Correct.
54 Correct 92 ms 105152 KB Correct.
55 Correct 87 ms 106432 KB Correct.
56 Correct 77 ms 104124 KB Correct.
57 Correct 72 ms 103804 KB Correct.
58 Correct 1916 ms 106072 KB Correct.
59 Correct 81 ms 102856 KB Correct.
60 Correct 90 ms 104768 KB Correct.
61 Correct 97 ms 105480 KB Correct.
62 Correct 89 ms 105264 KB Correct.
63 Correct 80 ms 105024 KB Correct.
64 Correct 120 ms 102732 KB Correct.
65 Correct 79 ms 104704 KB Correct.
66 Correct 99 ms 107012 KB Correct.
67 Correct 121 ms 109428 KB Correct.
68 Correct 89 ms 107196 KB Correct.
69 Correct 77 ms 104128 KB Correct.
70 Correct 81 ms 104096 KB Correct.
71 Correct 103 ms 110016 KB Correct.
72 Correct 80 ms 105664 KB Correct.
73 Correct 97 ms 109316 KB Correct.
74 Correct 106 ms 110144 KB Correct.
75 Correct 96 ms 108712 KB Correct.