QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376857#3172. Tomb Raiderckiseki#WA 0ms7408kbC++204.5kb2024-04-04 17:42:242024-04-04 17:42:24

Judging History

This is the latest submission verdict.

  • [2024-04-04 17:42:24]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 7408kb
  • [2024-04-04 17:42:24]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << "\n";
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

class DSU {
  vector<int> a;
public:
  DSU(int n) : a(n) {
    iota(all(a), 0);
  }
  int query(int x) {
    if (a[x] != x)
      a[x] = query(a[x]);
    return a[x];
  }
  void join(int x, int y) {
    debug("join", x, y);
    a[query(x)] = query(y);
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m; 
  vector<string> a(n);
  for (auto &ai : a)
    cin >> ai;

  constexpr int INF = 1 << 30;

  DSU dsu(n * m * 2 + 1);

  auto go = [&](int x, int y, int dx, int dy, int o) {
    debug("go", x, y, dx, dy);
    while (true) {
      x += dx, y += dy;
      if (x < 0 or x >= n) {
        x -= dx;
        dx = -dx;
      }
      if (y < 0 or y >= m) {
        y -= dy;
        dy = -dy;
      }
      debug("now", x, y);

      const int t = (x * m + y) * 2;
      if (a[x][y] == '/') {
        swap(dx, dy);
        dx = -dx, dy = -dy;
      } else if (a[x][y] == '\\') {
        swap(dx, dy);
      } else if (a[x][y] == '#') {
        dsu.join(o, n * m * 2);
        break;
      } else if (a[x][y] == 'V') {
        dsu.join(o, t + (dx == 0));
        dsu.join(o ^ 1, t + (dx != 0));
        break;
      } else if (a[x][y] == 'H') {
        dsu.join(o, t + (dy == 0));
        dsu.join(o ^ 1, t + (dy != 0));
        break;
      }
    }
  };

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      const int o = (i * m + j) * 2;
      if (a[i][j] == 'V') {
        go(i, j, -1, 0, o);
        go(i, j, 1, 0, o);
        go(i, j, 0, -1, o + 1);
        go(i, j, 0, 1, o + 1);
      } else if (a[i][j] == 'H') {
        go(i, j, -1, 0, o + 1);
        go(i, j, 1, 0, o + 1);
        go(i, j, 0, -1, o);
        go(i, j, 0, 1, o);
      }
    }
  }

  vector<int> cost(n * m * 2 + 1);

  debug(dsu.query(n * m * 2));
  cost[dsu.query(n * m * 2)] = INF;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (a[i][j] == 'V' or a[i][j] == 'H') {
        const int o = (i * m + j) * 2;
        debug(i, j, o, dsu.query(o), o + 1, dsu.query(o + 1));
        if (dsu.query(o) == dsu.query(o + 1)) {
          cout << "-1\n";
          return 0;
        }
        cost[dsu.query(o + 1)]++;
      }
    }
  }

  int64_t ans = 0;

  vector<bool> done(n * m * 2 + 1);

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (a[i][j] == 'V' or a[i][j] == 'H') {
        const int o = (i * m + j) * 2;
        if (not done[min(dsu.query(o), dsu.query(o + 1))]) {
          debug(i, j, cost[dsu.query(o)], cost[dsu.query(o + 1)]);
          ans += min(cost[dsu.query(o)], cost[dsu.query(o + 1)]);
          done[dsu.query(o)] = true;
          done[dsu.query(o + 1)] = true;
        }
      }
    }
  }

  cout << ans << '\n';

  return 0;
}

/*
1 3
H#H
("go", x, y, dx, dy) = (go, 0, 0, -1, 0)
("now", x, y) = (now, 0, 0)
("join", x, y) = (join, 1, 1)
("join", x, y) = (join, 0, 0)
("go", x, y, dx, dy) = (go, 0, 0, 1, 0)
("now", x, y) = (now, 0, 0)
("join", x, y) = (join, 1, 1)
("join", x, y) = (join, 0, 0)
("go", x, y, dx, dy) = (go, 0, 0, 0, -1)
("now", x, y) = (now, 0, 0)
("join", x, y) = (join, 0, 0)
("join", x, y) = (join, 1, 1)
("go", x, y, dx, dy) = (go, 0, 0, 0, 1)
("now", x, y) = (now, 0, 1)
("join", x, y) = (join, 0, 6)
("go", x, y, dx, dy) = (go, 0, 2, -1, 0)
("now", x, y) = (now, 0, 2)
("join", x, y) = (join, 5, 5)
("join", x, y) = (join, 4, 4)
("go", x, y, dx, dy) = (go, 0, 2, 1, 0)
("now", x, y) = (now, 0, 2)
("join", x, y) = (join, 5, 5)
("join", x, y) = (join, 4, 4)
("go", x, y, dx, dy) = (go, 0, 2, 0, -1)
("now", x, y) = (now, 0, 1)
("join", x, y) = (join, 4, 6)
("go", x, y, dx, dy) = (go, 0, 2, 0, 1)
("now", x, y) = (now, 0, 2)
("join", x, y) = (join, 4, 4)
("join", x, y) = (join, 5, 5)
(dsu.query(n * m * 2)) = (6)
(i, j, o, dsu.query(o), o + 1, dsu.query(o + 1)) = (0, 0, 0, 6, 1, 1)
(i, j, o, dsu.query(o), o + 1, dsu.query(o + 1)) = (0, 2, 4, 6, 5, 5)
(i, j, cost[dsu.query(o)], cost[dsu.query(o + 1)]) = (0, 0, 1073741824, 1)
1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3796kb

input:

5 5
/.V.\
./.V.
..#..
.V.#.
\.V./

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

2 5
V...\
H...V

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

2 2
VV
VV

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

4 3
/.\
H..
\H.
..H

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

5 5
.....
.H.V.
.....
.H.H.
.....

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

4 12
./.....\/.\.
.V\#/V./.#V\
/H/#\H../#H/
\........./.

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

4 12
./.....\/.\.
.V\#/V./.#V\
/H/#\H../#H/
\\......../.

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

2 2
#H
V#

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

2 2
V.
\#

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

2 2
V#
\#

output:

-1

result:

ok single line: '-1'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

3 5
V.#.\
./\..
\/\./

output:

-1

result:

ok single line: '-1'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

2 2
/#
H/

output:

-1

result:

ok single line: '-1'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

1 1
H

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

2 1
V
#

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

1 2
#H

output:

1

result:

ok single line: '1'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

5 5
V\#VH
H/#\/
#####
/\#/V
VH#\H

output:

4

result:

ok single line: '4'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

4 5
/.\/#
.///\
.\V/.
\.../

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

3 3
/\#
\.\
#\H

output:

-1

result:

ok single line: '-1'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

3 3
/\#
\V\
#\/

output:

-1

result:

ok single line: '-1'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

4 4
/..\
./\.
.H./
\./#

output:

-1

result:

ok single line: '-1'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

4 6
/.\...
....H\
..HHH.
\..../

output:

-1

result:

ok single line: '-1'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

4 4
/\/\
\/H/
/H/\
\/\/

output:

-1

result:

ok single line: '-1'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

6 6
../\..
..HH..
/H..V\
\H..H/
..HV..
..\/..

output:

2

result:

ok single line: '2'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

6 6
../\..
..HH#.
/H..V\
\H..H/
..HV#.
..\/..

output:

4

result:

ok single line: '4'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

6 6
../\..
..HH..
/H..V\
\H#.H/
..HV..
..\/..

output:

4

result:

ok single line: '4'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

3 2
V\
V.
\/

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

5 4
V.V\
/../
\..\
/../
V.V.

output:

-1

result:

ok single line: '-1'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

3 2
V#
..
VV

output:

-1

result:

ok single line: '-1'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

4 4
#V..
.VV.
..VV
...#

output:

-1

result:

ok single line: '-1'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

4 5
#V...
.VV\.
...VV
#...V

output:

-1

result:

ok single line: '-1'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

4 7
#V.../\
.VV..//
....//.
...VV.#

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

4 4
/\.H
\/#.
##//
V./V

output:

2

result:

ok single line: '2'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

4 4
H/\V
/VH\
\HH/
V\/H

output:

1

result:

ok single line: '1'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

2 4
/V\\
\\.V

output:

1

result:

ok single line: '1'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

2 3
/V\
\.V

output:

-1

result:

ok single line: '-1'

Test #36:

score: -100
Wrong Answer
time: 0ms
memory: 7408kb

input:

500 500
V...V.....H.......H.......V.......................H...V.H.......V.....H.V...V.........V.......H.........V...................H.....................H.H.................................V.................H.......V.........V...V.H.V.H.....H.......V.........V.V.V.....V...................H.......V....

output:

5072

result:

wrong answer 1st lines differ - expected: '6264', found: '5072'