Submission #640002

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
640002	2022-09-13T07:35:36 Z	alextm	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1245 ms	123660 KB

tracks

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

const int MAXN = 4001;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

char mat[MAXN][MAXN];
int dist[MAXN][MAXN], n, m;

bool inside(int x, int y) {
  return (x >= 1 && x <= n && y >= 1 && y <= m && mat[x][y] != '.');
}

int main() {
  cin >> n >> m;
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
      cin >> mat[i][j];

  deque<pair<int,int>> dq;
  dq.emplace_back(1, 1);
  dist[1][1] = 1;

  int answer = 1;
  while(!dq.empty()) {
    int l = dq.front().first;
    int c = dq.front().second;
    dq.pop_front();
    answer = max(answer, dist[l][c]);

    for(int k = 0; k < 4; k++) {
      int nxtl = l + dx[k];
      int nxtc = c + dy[k];
      if(inside(nxtl, nxtc) && !dist[nxtl][nxtc]) {
        if(mat[l][c] != mat[nxtl][nxtc]) { // weight 1
          dist[nxtl][nxtc] = dist[l][c] + 1;
          dq.emplace_back(nxtl, nxtc);
        } else {
          dist[nxtl][nxtc] = dist[l][c];
          dq.push_front({nxtl, nxtc});
        }
      }
    }
  }

  cout << answer << '\n';

  return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	5332 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	724 KB	Output is correct
4	Correct	14 ms	5180 KB	Output is correct
5	Correct	7 ms	2900 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	2 ms	1108 KB	Output is correct
10	Correct	7 ms	2388 KB	Output is correct
11	Correct	5 ms	2132 KB	Output is correct
12	Correct	9 ms	3008 KB	Output is correct
13	Correct	7 ms	2868 KB	Output is correct
14	Correct	7 ms	2900 KB	Output is correct
15	Correct	21 ms	5196 KB	Output is correct
16	Correct	21 ms	5312 KB	Output is correct
17	Correct	19 ms	5196 KB	Output is correct
18	Correct	13 ms	5076 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	30784 KB	Output is correct
2	Correct	112 ms	15036 KB	Output is correct
3	Correct	1065 ms	73492 KB	Output is correct
4	Correct	249 ms	32596 KB	Output is correct
5	Correct	563 ms	53360 KB	Output is correct
6	Correct	1245 ms	107536 KB	Output is correct
7	Correct	18 ms	32212 KB	Output is correct
8	Correct	21 ms	30732 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	18 ms	31612 KB	Output is correct
12	Correct	3 ms	1524 KB	Output is correct
13	Correct	111 ms	15016 KB	Output is correct
14	Correct	71 ms	10292 KB	Output is correct
15	Correct	68 ms	13060 KB	Output is correct
16	Correct	47 ms	5600 KB	Output is correct
17	Correct	282 ms	28728 KB	Output is correct
18	Correct	262 ms	35592 KB	Output is correct
19	Correct	269 ms	32664 KB	Output is correct
20	Correct	226 ms	25548 KB	Output is correct
21	Correct	563 ms	52680 KB	Output is correct
22	Correct	562 ms	53212 KB	Output is correct
23	Correct	533 ms	43820 KB	Output is correct
24	Correct	561 ms	49648 KB	Output is correct
25	Correct	1077 ms	94348 KB	Output is correct
26	Correct	880 ms	123660 KB	Output is correct
27	Correct	1163 ms	111804 KB	Output is correct
28	Correct	1226 ms	107308 KB	Output is correct
29	Correct	1228 ms	96928 KB	Output is correct
30	Correct	1211 ms	107016 KB	Output is correct
31	Correct	885 ms	73328 KB	Output is correct
32	Correct	1094 ms	98144 KB	Output is correct