Submission #20102526

Source Code Expand

#include <atcoder/dsu>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  for (auto &s : S)
    cin >> s;
  S[0][0] = S[0][W - 1] = S[H - 1][0] = S[H - 1][W - 1] = '#';

  dsu d(H + W);
  for (int r = 0; r < H; ++r)
    for (int c = 0; c < W; ++c)
      if (S[r][c] == '#')
        d.merge(r, H + c);

  unordered_set<int> row, col;
  for (int r = 0; r < H; ++r)
    row.insert(d.leader(r));
  for (int c = 0; c < W; ++c)
    col.insert(d.leader(H + c));

  cout << min(row.size() - 1, col.size() - 1) << endl;

  return 0;
}

Submission Info

Submission Time
Task D - Skate
User nuip
Language C++ (GCC 9.2.1)
Score 600
Code Size 645 Byte
Status AC
Exec Time 37 ms
Memory 5600 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 37
Set Name Test Cases
Sample sample.txt, sample_2.txt
All complete_1000_1000.txt, complete_1000_1000_1.txt, complete_1000_1000_10.txt, complete_1000_1000_100.txt, complete_1000_1000_1000.txt, complete_1000_1000_3.txt, complete_1000_1000_333.txt, complete_1000_1000_5.txt, complete_1000_1000_7.txt, horizontal_820_2_1.txt, horizontal_86_2_2.txt, horizontal_892_2_0.txt, random_1000_1000.txt, random_1000_1000_2.txt, random_1000_1000_3.txt, random_1000_1000_4.txt, random_1000_1000_5.txt, random_391_910.txt, random_423_172.txt, random_45_809.txt, random_461_111.txt, random_740_398.txt, sample.txt, sample_2.txt, sparse_261_351.txt, sparse_292_662.txt, sparse_372_354.txt, sparse_381_830.txt, sparse_432_398.txt, sparse_626_931.txt, sparse_73_682.txt, sparse_801_149.txt, sparse_820_852.txt, sparse_85_950.txt, vertical_2_113_1.txt, vertical_2_304_2.txt, vertical_2_710_0.txt
Case Name Status Exec Time Memory
complete_1000_1000.txt AC 37 ms 5528 KiB
complete_1000_1000_1.txt AC 26 ms 5424 KiB
complete_1000_1000_10.txt AC 31 ms 5400 KiB
complete_1000_1000_100.txt AC 31 ms 5412 KiB
complete_1000_1000_1000.txt AC 25 ms 5572 KiB
complete_1000_1000_3.txt AC 27 ms 5520 KiB
complete_1000_1000_333.txt AC 30 ms 5508 KiB
complete_1000_1000_5.txt AC 30 ms 5508 KiB
complete_1000_1000_7.txt AC 32 ms 5512 KiB
horizontal_820_2_1.txt AC 5 ms 3520 KiB
horizontal_86_2_2.txt AC 5 ms 3472 KiB
horizontal_892_2_0.txt AC 3 ms 3456 KiB
random_1000_1000.txt AC 28 ms 5600 KiB
random_1000_1000_2.txt AC 29 ms 5560 KiB
random_1000_1000_3.txt AC 24 ms 5436 KiB
random_1000_1000_4.txt AC 31 ms 5524 KiB
random_1000_1000_5.txt AC 32 ms 5568 KiB
random_391_910.txt AC 12 ms 3880 KiB
random_423_172.txt AC 6 ms 3560 KiB
random_45_809.txt AC 3 ms 3528 KiB
random_461_111.txt AC 6 ms 3544 KiB
random_740_398.txt AC 16 ms 3900 KiB
sample.txt AC 5 ms 3548 KiB
sample_2.txt AC 2 ms 3600 KiB
sparse_261_351.txt AC 6 ms 3612 KiB
sparse_292_662.txt AC 8 ms 3916 KiB
sparse_372_354.txt AC 8 ms 3824 KiB
sparse_381_830.txt AC 18 ms 3996 KiB
sparse_432_398.txt AC 7 ms 3840 KiB
sparse_626_931.txt AC 18 ms 4300 KiB
sparse_73_682.txt AC 5 ms 3680 KiB
sparse_801_149.txt AC 8 ms 3716 KiB
sparse_820_852.txt AC 19 ms 4468 KiB
sparse_85_950.txt AC 5 ms 3740 KiB
vertical_2_113_1.txt AC 2 ms 3556 KiB
vertical_2_304_2.txt AC 3 ms 3464 KiB
vertical_2_710_0.txt AC 2 ms 3560 KiB