oj.uz

Submission #212307

# Submission time Handle Problem Language Result Execution time Memory
212307 2020-03-22T17:01:34 Z model_code Skandi (COCI20_skandi) C++17
110 / 110
 4288 ms 20732 KB 
#include <bits/stdc++.h>

using namespace std;

#define TRACE(x) cerr << #x << " " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<

typedef long long llint;

const int MAXN = 505;

int R, S, hor, ver;
char grid[MAXN][MAXN];

map<pair<int, int>, int> hor_id, ver_id;
map<int, pair<int, int>> hor_coord, ver_coord;

vector<int> matchV, matchH;
vector<bool> bio, coverV, coverH;
vector<vector<int>> G;

inline void build_graph() {
  for (int i = 0; i < R; ++i) {
    for (int j = 0; j < S; ++j) {
      if (grid[i][j] == '0') continue;
      if (i + 1 < R && grid[i + 1][j] == '0') {
        ver_id[{i, j}] = ver;
        ver_coord[ver++] = {i + 1, j + 1};
      }
      if (j + 1 < S && grid[i][j + 1] == '0') {
        hor_id[{i, j}] = hor;
        hor_coord[hor++] = {i + 1, j + 1};
      }
    }
  }

  G.resize(ver_id.size());
  for (int i = 0; i < R; ++i) {
    for (int j = 0; j < S; ++j) {
      if (grid[i][j] == '1') continue;
      int _i = i - 1, _j = j - 1;
      while (grid[_i][j] == '0') --_i;
      while (grid[i][_j] == '0') --_j;
      G[ver_id[{_i, j}]].push_back(hor_id[{i, _j}]);
    }
  }
}

bool dfs(int node) {
  if (bio[node]) return false;
  bio[node] = true;
  for (int i : G[node]) {
    if (matchH[i] == -1 || dfs(matchH[i])) {
      matchH[i] = node;
      return true;
    }
  }
  return false;
}

int matching() {
  bio.resize(ver_id.size(), false);
  matchV.resize(ver_id.size(), -1);
  matchH.resize(hor_id.size(), -1);
  int ret = 0;
  for (int i = 0; i < (int)ver_id.size(); ++i) {
    fill(bio.begin(), bio.end(), false);
    ret += dfs(i);
  }
  return ret;
}

void alternate(int node) {
  coverV[node] = true;
  for (int i : G[node]) {
    if (coverH[i]) continue;
    assert(matchH[i] != -1);
    coverH[i] = true;
    alternate(matchH[i]);
  }
}

void vertex_cover() {
  coverV.resize(ver_id.size(), false);
  coverH.resize(hor_id.size(), false);
  for (int i = 0; i < (int)hor_id.size(); ++i) {
    if (matchH[i] != -1)
      matchV[matchH[i]] = i;
  }
  for (int i = 0; i < (int)ver_id.size(); ++i) {
    if (matchV[i] != -1) continue;
    alternate(i);
  }
}

void reconstruct() {
  for (int i = 0; i < (int)ver_id.size(); ++i) {
    const auto &coord = ver_coord[i];
    if (!coverV[i]) printf("%d %d DOLJE\n", coord.first, coord.second);
  }
  for (int i = 0; i < (int)hor_id.size(); ++i) {
    const auto &coord = hor_coord[i];
    if (coverH[i]) printf("%d %d DESNO\n", coord.first, coord.second);
  }
}

int main(void) {
  scanf("%d%d", &R, &S);
  for (int i = 0; i < R; ++i)
    scanf("%s", grid[i]);

  build_graph();
  printf("%d\n", matching());

  vertex_cover();
  reconstruct();

  return 0;
}

Compilation message

skandi.cpp: In function 'int main()':
skandi.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &R, &S);
   ~~~~~^~~~~~~~~~~~~~~~
skandi.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", grid[i]);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correct.
2 Correct 6 ms 256 KB Correct.
3 Correct 5 ms 256 KB Correct.
4 Correct 5 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.
6 Correct 5 ms 384 KB Correct.
7 Correct 4 ms 256 KB Correct.
8 Correct 5 ms 256 KB Correct.
9 Correct 5 ms 256 KB Correct.
10 Correct 5 ms 304 KB Correct.
11 Correct 5 ms 256 KB Correct.
12 Correct 4 ms 256 KB Correct.
13 Correct 5 ms 512 KB Correct.
14 Correct 5 ms 256 KB Correct.
15 Correct 5 ms 360 KB Correct.
16 Correct 5 ms 384 KB Correct.
17 Correct 5 ms 436 KB Correct.
18 Correct 5 ms 256 KB Correct.
19 Correct 5 ms 384 KB Correct.
20 Correct 5 ms 384 KB Correct.
21 Correct 5 ms 256 KB Correct.
22 Correct 5 ms 360 KB Correct.
23 Correct 5 ms 256 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Correct.
2 Correct 5 ms 512 KB Correct.
3 Correct 5 ms 640 KB Correct.
4 Correct 5 ms 384 KB Correct.
5 Correct 5 ms 512 KB Correct.
6 Correct 5 ms 384 KB Correct.
7 Correct 5 ms 384 KB Correct.
8 Correct 6 ms 544 KB Correct.
9 Correct 6 ms 640 KB Correct.
10 Correct 7 ms 896 KB Correct.
11 Correct 8 ms 1024 KB Correct.
12 Correct 8 ms 896 KB Correct.
13 Correct 7 ms 896 KB Correct.
14 Correct 7 ms 1024 KB Correct.
15 Correct 8 ms 896 KB Correct.
16 Correct 8 ms 1076 KB Correct.
17 Correct 7 ms 896 KB Correct.
18 Correct 6 ms 896 KB Correct.
19 Correct 7 ms 1024 KB Correct.
20 Correct 7 ms 896 KB Correct.
21 Correct 8 ms 896 KB Correct.
22 Correct 7 ms 980 KB Correct.
23 Correct 9 ms 896 KB Correct.
24 Correct 6 ms 768 KB Correct.
25 Correct 7 ms 896 KB Correct.
26 Correct 7 ms 896 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correct.
2 Correct 6 ms 256 KB Correct.
3 Correct 5 ms 256 KB Correct.
4 Correct 5 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.
6 Correct 5 ms 384 KB Correct.
7 Correct 4 ms 256 KB Correct.
8 Correct 5 ms 256 KB Correct.
9 Correct 5 ms 256 KB Correct.
10 Correct 5 ms 304 KB Correct.
11 Correct 5 ms 256 KB Correct.
12 Correct 4 ms 256 KB Correct.
13 Correct 5 ms 512 KB Correct.
14 Correct 5 ms 256 KB Correct.
15 Correct 5 ms 360 KB Correct.
16 Correct 5 ms 384 KB Correct.
17 Correct 5 ms 436 KB Correct.
18 Correct 5 ms 256 KB Correct.
19 Correct 5 ms 384 KB Correct.
20 Correct 5 ms 384 KB Correct.
21 Correct 5 ms 256 KB Correct.
22 Correct 5 ms 360 KB Correct.
23 Correct 5 ms 256 KB Correct.
24 Correct 5 ms 512 KB Correct.
25 Correct 5 ms 512 KB Correct.
26 Correct 5 ms 640 KB Correct.
27 Correct 5 ms 384 KB Correct.
28 Correct 5 ms 512 KB Correct.
29 Correct 5 ms 384 KB Correct.
30 Correct 5 ms 384 KB Correct.
31 Correct 6 ms 544 KB Correct.
32 Correct 6 ms 640 KB Correct.
33 Correct 7 ms 896 KB Correct.
34 Correct 8 ms 1024 KB Correct.
35 Correct 8 ms 896 KB Correct.
36 Correct 7 ms 896 KB Correct.
37 Correct 7 ms 1024 KB Correct.
38 Correct 8 ms 896 KB Correct.
39 Correct 8 ms 1076 KB Correct.
40 Correct 7 ms 896 KB Correct.
41 Correct 6 ms 896 KB Correct.
42 Correct 7 ms 1024 KB Correct.
43 Correct 7 ms 896 KB Correct.
44 Correct 8 ms 896 KB Correct.
45 Correct 7 ms 980 KB Correct.
46 Correct 9 ms 896 KB Correct.
47 Correct 6 ms 768 KB Correct.
48 Correct 7 ms 896 KB Correct.
49 Correct 7 ms 896 KB Correct.
50 Correct 131 ms 17308 KB Correct.
51 Correct 4288 ms 6220 KB Correct.
52 Correct 223 ms 17784 KB Correct.
53 Correct 132 ms 17400 KB Correct.
54 Correct 137 ms 15360 KB Correct.
55 Correct 198 ms 19704 KB Correct.
56 Correct 159 ms 18664 KB Correct.
57 Correct 138 ms 18168 KB Correct.
58 Correct 2824 ms 5076 KB Correct.
59 Correct 135 ms 15992 KB Correct.
60 Correct 144 ms 18400 KB Correct.
61 Correct 141 ms 13108 KB Correct.
62 Correct 148 ms 18552 KB Correct.
63 Correct 147 ms 18680 KB Correct.
64 Correct 190 ms 1912 KB Correct.
65 Correct 142 ms 18552 KB Correct.
66 Correct 152 ms 15224 KB Correct.
67 Correct 181 ms 15480 KB Correct.
68 Correct 169 ms 19680 KB Correct.
69 Correct 147 ms 17760 KB Correct.
70 Correct 147 ms 18040 KB Correct.
71 Correct 159 ms 18936 KB Correct.
72 Correct 157 ms 19704 KB Correct.
73 Correct 161 ms 20216 KB Correct.
74 Correct 162 ms 18296 KB Correct.
75 Correct 169 ms 20732 KB Correct.