Submission #988483

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
988483	2024-05-24T22:02:48 Z	kflippy	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1087 ms	125020 KB

tracks

#include <bits/stdc++.h>

using namespace std;

int h, w;
char s[4000][4000];

bool chk(pair<int, int> c)
{
  return c.first > -1 && c.first < h && c.second < w && c.second > -1 && s[c.first][c.second] != '.';
}

int
main()
{
  cin >> h >> w;
  deque<pair<int, int>> q;
  vector<vector<int>> d(h, vector<int>(w));
  d[0][0] = 1;
  for(int i = 0; i < h; ++i) {
    for(int j = 0; j < w; ++j) {
      cin >> s[i][j];
    }
  }
  q.push_front({0, 0});
  vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
  int ans = 0;
  while(!q.empty()) {
    pair<int, int> x = q.front();
    q.pop_front();
    ans = max(ans, d[x.first][x.second]);
    for(int i = 0; i < 4; ++i) {
      pair<int, int> y = {x.first + dx[i], x.second + dy[i]};
      if(chk(y) && d[y.first][y.second] == 0) {
        if(s[y.first][y.second] == s[x.first][x.second]) {
          d[y.first][y.second] = d[x.first][x.second];
          q.push_front({y.first, y.second});
        }
        else {
          d[y.first][y.second] = d[x.first][x.second] + 1;
          q.push_back({y.first, y.second});
        }
      }
    }
  }
  cout << ans << "\n";
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	3932 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	10 ms	3420 KB	Output is correct
5	Correct	5 ms	2908 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	2652 KB	Output is correct
8	Correct	3 ms	2652 KB	Output is correct
9	Correct	3 ms	2804 KB	Output is correct
10	Correct	4 ms	2908 KB	Output is correct
11	Correct	4 ms	2908 KB	Output is correct
12	Correct	6 ms	2908 KB	Output is correct
13	Correct	5 ms	2908 KB	Output is correct
14	Correct	6 ms	2908 KB	Output is correct
15	Correct	15 ms	3932 KB	Output is correct
16	Correct	16 ms	3672 KB	Output is correct
17	Correct	13 ms	3676 KB	Output is correct
18	Correct	10 ms	3416 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	15708 KB	Output is correct
2	Correct	75 ms	14448 KB	Output is correct
3	Correct	636 ms	94624 KB	Output is correct
4	Correct	168 ms	27124 KB	Output is correct
5	Correct	362 ms	57052 KB	Output is correct
6	Correct	1087 ms	109420 KB	Output is correct
7	Correct	5 ms	16472 KB	Output is correct
8	Correct	5 ms	15708 KB	Output is correct
9	Correct	4 ms	600 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	6 ms	16120 KB	Output is correct
12	Correct	3 ms	2652 KB	Output is correct
13	Correct	75 ms	14440 KB	Output is correct
14	Correct	44 ms	9156 KB	Output is correct
15	Correct	42 ms	9564 KB	Output is correct
16	Correct	36 ms	5784 KB	Output is correct
17	Correct	200 ms	28692 KB	Output is correct
18	Correct	173 ms	28240 KB	Output is correct
19	Correct	168 ms	27220 KB	Output is correct
20	Correct	139 ms	25700 KB	Output is correct
21	Correct	380 ms	58708 KB	Output is correct
22	Correct	352 ms	57188 KB	Output is correct
23	Correct	383 ms	48920 KB	Output is correct
24	Correct	360 ms	57396 KB	Output is correct
25	Correct	873 ms	94588 KB	Output is correct
26	Correct	678 ms	125020 KB	Output is correct
27	Correct	910 ms	123820 KB	Output is correct
28	Correct	1034 ms	109044 KB	Output is correct
29	Correct	1040 ms	105396 KB	Output is correct
30	Correct	931 ms	112536 KB	Output is correct
31	Correct	640 ms	65612 KB	Output is correct
32	Correct	907 ms	114080 KB	Output is correct