답안 #981038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981038	2024-05-12T18:06:43 Z	kilkuwu	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1238 ms	189532 KB

tracks

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int N, M;
  std::cin >> N >> M;
  std::vector<std::string> s(N);
  for (int i = 0; i < N; i++) {
    std::cin >> s[i];
  }

  std::vector vis(N, std::vector<int>(M));
  auto nqg = vis;

  const std::vector<std::pair<int, int>> dxy = {
    {0, -1},
    {0, 1},
    {-1, 0},
    {1, 0}
  };

  auto valid = [&](int x, int y) {
    return 0 <= x && x < N && 0 <= y && y < M;
  };
  std::queue<std::pair<int, int>> q;
  q.push({0, 0});
  vis[0][0] = 1;
  int cnt =0 ;
  while (q.size()) {
    dbg(q);
    cnt++;
    std::vector<std::pair<int, int>> nq;
    while (q.size()) {
      auto [x, y] = q.front();
      q.pop();

      for (auto [dx, dy] : dxy) {
        int nx = x + dx, ny = y + dy;
        if (!valid(nx, ny)) continue;
        if (vis[nx][ny]) continue;
        if (s[nx][ny] == '.') continue;
        if (s[nx][ny] == s[x][y]) {
          q.emplace(nx, ny);
          vis[nx][ny] = 1;
        } else {
          if (nqg[nx][ny]) continue;
          nq.emplace_back(nx, ny);
          nqg[nx][ny] = 1;
        }
      }
    }

    std::queue<std::pair<int, int>> gg;
    for (auto [x, y] : nq) {
      vis[x][y] = 1;
      gg.emplace(x, y);
    }
    std::swap(gg, q);
  }

  std::cout << cnt << nl;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	2904 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	456 KB	Output is correct
4	Correct	6 ms	2264 KB	Output is correct
5	Correct	2 ms	1112 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	428 KB	Output is correct
10	Correct	2 ms	1116 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct
12	Correct	6 ms	1372 KB	Output is correct
13	Correct	2 ms	1116 KB	Output is correct
14	Correct	2 ms	1112 KB	Output is correct
15	Correct	10 ms	2988 KB	Output is correct
16	Correct	12 ms	2904 KB	Output is correct
17	Correct	7 ms	2652 KB	Output is correct
18	Correct	6 ms	2268 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1116 KB	Output is correct
2	Correct	44 ms	16004 KB	Output is correct
3	Correct	245 ms	159640 KB	Output is correct
4	Correct	65 ms	37460 KB	Output is correct
5	Correct	328 ms	89684 KB	Output is correct
6	Correct	1079 ms	189532 KB	Output is correct
7	Correct	2 ms	1116 KB	Output is correct
8	Correct	2 ms	1148 KB	Output is correct
9	Correct	2 ms	860 KB	Output is correct
10	Correct	1 ms	720 KB	Output is correct
11	Correct	1 ms	1116 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	46 ms	16020 KB	Output is correct
14	Correct	24 ms	9308 KB	Output is correct
15	Correct	19 ms	10328 KB	Output is correct
16	Correct	23 ms	6748 KB	Output is correct
17	Correct	140 ms	40484 KB	Output is correct
18	Correct	83 ms	40016 KB	Output is correct
19	Correct	64 ms	37460 KB	Output is correct
20	Correct	58 ms	34568 KB	Output is correct
21	Correct	147 ms	92860 KB	Output is correct
22	Correct	312 ms	89936 KB	Output is correct
23	Correct	277 ms	77324 KB	Output is correct
24	Correct	175 ms	90756 KB	Output is correct
25	Correct	558 ms	159312 KB	Output is correct
26	Correct	417 ms	122228 KB	Output is correct
27	Correct	697 ms	162500 KB	Output is correct
28	Correct	1238 ms	189324 KB	Output is correct
29	Correct	1117 ms	181860 KB	Output is correct
30	Correct	899 ms	178680 KB	Output is correct
31	Correct	933 ms	103428 KB	Output is correct
32	Correct	595 ms	160972 KB	Output is correct