Submission #359017

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
359017	2021-01-26T09:06:38 Z	betterdanjoe	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	1528 ms	137360 KB

tracks

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

int moves[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

int main(){
  int n, m;
  cin >> n >> m;
  char arr[n][m];
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> arr[i][j];
    }
  }
  int num[n][m];
  memset(num, 0, sizeof(num));
  num[0][0] = 1;
  deque<pair<int, int>> q;
  q.push_back({0, 0});
  int ans = 0;
  while(!q.empty()){
    pair<int, int> x = q.front();
    q.pop_front();
    ans = max(num[x.first][x.second], ans);
    for(int i = 0; i < 4; i++){
      int x1 = x.first + moves[i][0], y1 = x.second + moves[i][1];
      if(x1 < 0 || y1 < 0 || x1 >= n || y1 >= m || num[x1][y1] != 0 || arr[x1][y1] == '.') continue;
      if(arr[x1][y1] != arr[x.first][x.second]){
        num[x1][y1] = num[x.first][x.second] + 1;
        q.push_back({x1, y1});
      } else {
        num[x1][y1] = num[x.first][x.second];
        q.push_front({x1, y1});
      }
    }
  }
  cout << ans << endl;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	1772 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	15 ms	1516 KB	Output is correct
5	Correct	7 ms	748 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	6 ms	748 KB	Output is correct
11	Correct	5 ms	620 KB	Output is correct
12	Correct	9 ms	876 KB	Output is correct
13	Correct	7 ms	748 KB	Output is correct
14	Correct	7 ms	876 KB	Output is correct
15	Correct	23 ms	1772 KB	Output is correct
16	Correct	24 ms	1772 KB	Output is correct
17	Correct	25 ms	1772 KB	Output is correct
18	Correct	18 ms	1516 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	620 KB	Output is correct
2	Correct	134 ms	9600 KB	Output is correct
3	Correct	1122 ms	94348 KB	Output is correct
4	Correct	289 ms	22380 KB	Output is correct
5	Correct	662 ms	53100 KB	Output is correct
6	Correct	1528 ms	108840 KB	Output is correct
7	Correct	4 ms	620 KB	Output is correct
8	Correct	4 ms	620 KB	Output is correct
9	Correct	5 ms	620 KB	Output is correct
10	Correct	3 ms	492 KB	Output is correct
11	Correct	4 ms	620 KB	Output is correct
12	Correct	2 ms	492 KB	Output is correct
13	Correct	128 ms	9452 KB	Output is correct
14	Correct	71 ms	5612 KB	Output is correct
15	Correct	74 ms	6124 KB	Output is correct
16	Correct	55 ms	4204 KB	Output is correct
17	Correct	338 ms	24172 KB	Output is correct
18	Correct	299 ms	23788 KB	Output is correct
19	Correct	289 ms	22508 KB	Output is correct
20	Correct	244 ms	20460 KB	Output is correct
21	Correct	653 ms	55020 KB	Output is correct
22	Correct	693 ms	53228 KB	Output is correct
23	Correct	699 ms	45932 KB	Output is correct
24	Correct	660 ms	53740 KB	Output is correct
25	Correct	1342 ms	94444 KB	Output is correct
26	Correct	1421 ms	122412 KB	Output is correct
27	Correct	1482 ms	137360 KB	Output is correct
28	Correct	1515 ms	108752 KB	Output is correct
29	Correct	1495 ms	106056 KB	Output is correct
30	Correct	1490 ms	112812 KB	Output is correct
31	Correct	1132 ms	61036 KB	Output is correct
32	Correct	1520 ms	117280 KB	Output is correct