oj.uz

Submission #258430

# Submission time Handle Problem Language Result Execution time Memory
258430 2020-08-05T23:03:09 Z ipaljak Skandi (COCI20_skandi) C++14
110 / 110
 3997 ms 20984 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 0 ms 256 KB Correct.
2 Correct 0 ms 256 KB Correct.
3 Correct 0 ms 256 KB Correct.
4 Correct 0 ms 384 KB Correct.
5 Correct 0 ms 256 KB Correct.
6 Correct 0 ms 256 KB Correct.
7 Correct 0 ms 256 KB Correct.
8 Correct 0 ms 256 KB Correct.
9 Correct 0 ms 256 KB Correct.
10 Correct 0 ms 256 KB Correct.
11 Correct 1 ms 384 KB Correct.
12 Correct 0 ms 256 KB Correct.
13 Correct 0 ms 256 KB Correct.
14 Correct 1 ms 256 KB Correct.
15 Correct 1 ms 256 KB Correct.
16 Correct 0 ms 368 KB Correct.
17 Correct 1 ms 256 KB Correct.
18 Correct 0 ms 256 KB Correct.
19 Correct 1 ms 256 KB Correct.
20 Correct 0 ms 256 KB Correct.
21 Correct 1 ms 384 KB Correct.
22 Correct 1 ms 256 KB Correct.
23 Correct 0 ms 256 KB Correct.

Subtask #2
32.0 / 32.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Correct.
2 Correct 0 ms 256 KB Correct.
3 Correct 0 ms 256 KB Correct.
4 Correct 0 ms 384 KB Correct.
5 Correct 0 ms 256 KB Correct.
6 Correct 0 ms 256 KB Correct.
7 Correct 0 ms 256 KB Correct.
8 Correct 0 ms 256 KB Correct.
9 Correct 0 ms 256 KB Correct.
10 Correct 0 ms 256 KB Correct.
11 Correct 1 ms 384 KB Correct.
12 Correct 0 ms 256 KB Correct.
13 Correct 0 ms 256 KB Correct.
14 Correct 1 ms 256 KB Correct.
15 Correct 1 ms 256 KB Correct.
16 Correct 0 ms 368 KB Correct.
17 Correct 1 ms 256 KB Correct.
18 Correct 0 ms 256 KB Correct.
19 Correct 1 ms 256 KB Correct.
20 Correct 0 ms 256 KB Correct.
21 Correct 1 ms 384 KB Correct.
22 Correct 1 ms 256 KB Correct.
23 Correct 0 ms 256 KB Correct.
24 Correct 1 ms 512 KB Correct.
25 Correct 1 ms 384 KB Correct.
26 Correct 1 ms 640 KB Correct.
27 Correct 1 ms 384 KB Correct.
28 Correct 1 ms 512 KB Correct.
29 Correct 1 ms 384 KB Correct.
30 Correct 1 ms 384 KB Correct.
31 Correct 2 ms 512 KB Correct.
32 Correct 2 ms 640 KB Correct.
33 Correct 3 ms 896 KB Correct.
34 Correct 3 ms 1024 KB Correct.
35 Correct 3 ms 896 KB Correct.
36 Correct 2 ms 1024 KB Correct.
37 Correct 3 ms 1024 KB Correct.
38 Correct 3 ms 896 KB Correct.
39 Correct 3 ms 896 KB Correct.
40 Correct 3 ms 896 KB Correct.
41 Correct 3 ms 896 KB Correct.
42 Correct 2 ms 1024 KB Correct.
43 Correct 2 ms 896 KB Correct.
44 Correct 2 ms 896 KB Correct.
45 Correct 3 ms 1024 KB Correct.
46 Correct 3 ms 1024 KB Correct.
47 Correct 2 ms 768 KB Correct.
48 Correct 3 ms 896 KB Correct.
49 Correct 3 ms 1024 KB Correct.
50 Correct 128 ms 17552 KB Correct.
51 Correct 3997 ms 6768 KB Correct.
52 Correct 144 ms 17912 KB Correct.
53 Correct 125 ms 17656 KB Correct.
54 Correct 125 ms 15608 KB Correct.
55 Correct 150 ms 19960 KB Correct.
56 Correct 132 ms 18808 KB Correct.
57 Correct 127 ms 18424 KB Correct.
58 Correct 2546 ms 5504 KB Correct.
59 Correct 120 ms 16124 KB Correct.
60 Correct 136 ms 18680 KB Correct.
61 Correct 133 ms 13304 KB Correct.
62 Correct 141 ms 18816 KB Correct.
63 Correct 142 ms 18844 KB Correct.
64 Correct 194 ms 2040 KB Correct.
65 Correct 134 ms 18788 KB Correct.
66 Correct 132 ms 15480 KB Correct.
67 Correct 147 ms 15612 KB Correct.
68 Correct 152 ms 19920 KB Correct.
69 Correct 139 ms 17912 KB Correct.
70 Correct 151 ms 18228 KB Correct.
71 Correct 160 ms 19192 KB Correct.
72 Correct 149 ms 19960 KB Correct.
73 Correct 173 ms 20472 KB Correct.
74 Correct 151 ms 18552 KB Correct.
75 Correct 165 ms 20984 KB Correct.