답안 #748310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748310	2023-05-26T05:22:28 Z	54skyxenon	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	698 ms	175804 KB

tracks

// https://oj.uz/problem/view/BOI13_tracks
 
#include <bits/stdc++.h>
using namespace std;
 
#define tiii tuple<int, int, int>
#define mp make_pair
#define mt make_tuple
#define maxHW 4000
 
bool seen[maxHW][maxHW];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int h, w;
    cin >> h >> w;
 
    vector<string> grid(h);
    for (int i = 0; i < h; i++) {
        cin >> grid[i];
    }
 
    int ans = 0;
 
    deque<tiii> Q({mt(0, 0, 1)});
    while (!Q.empty()) {
        auto [r, c, depth] = Q.front(); Q.pop_front();
        ans = max(ans, depth);
        seen[r][c] = true;
 
        for (auto [nr, nc] : {mp(r + 1, c), mp(r - 1, c), mp(r, c + 1), mp(r, c - 1)}) {
            if (0 <= nr && nr < h && 0 <= nc && nc < w && !seen[nr][nc] && grid[nr][nc] != '.') {
                if (grid[nr][nc] == grid[r][c]) {
                    Q.push_front(mt(nr, nc, depth));
                }
                else {
                    Q.push_back(mt(nr, nc, depth + 1));
                }
            }
        }
    }
 
    cout << ans << '\n';
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	2644 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	8 ms	3092 KB	Output is correct
5	Correct	3 ms	1492 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	468 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	1 ms	768 KB	Output is correct
10	Correct	3 ms	1364 KB	Output is correct
11	Correct	3 ms	1236 KB	Output is correct
12	Correct	6 ms	1620 KB	Output is correct
13	Correct	2 ms	1492 KB	Output is correct
14	Correct	2 ms	1492 KB	Output is correct
15	Correct	13 ms	2644 KB	Output is correct
16	Correct	15 ms	2764 KB	Output is correct
17	Correct	9 ms	2388 KB	Output is correct
18	Correct	8 ms	3096 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	15372 KB	Output is correct
2	Correct	42 ms	6868 KB	Output is correct
3	Correct	171 ms	33644 KB	Output is correct
4	Correct	42 ms	11604 KB	Output is correct
5	Correct	79 ms	21780 KB	Output is correct
6	Correct	698 ms	82640 KB	Output is correct
7	Correct	10 ms	16084 KB	Output is correct
8	Correct	10 ms	15316 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	10 ms	15708 KB	Output is correct
12	Correct	1 ms	852 KB	Output is correct
13	Correct	40 ms	6868 KB	Output is correct
14	Correct	23 ms	4820 KB	Output is correct
15	Correct	10 ms	5204 KB	Output is correct
16	Correct	22 ms	2648 KB	Output is correct
17	Correct	101 ms	12632 KB	Output is correct
18	Correct	39 ms	12372 KB	Output is correct
19	Correct	42 ms	11680 KB	Output is correct
20	Correct	42 ms	10836 KB	Output is correct
21	Correct	103 ms	22608 KB	Output is correct
22	Correct	77 ms	21828 KB	Output is correct
23	Correct	196 ms	18660 KB	Output is correct
24	Correct	75 ms	22368 KB	Output is correct
25	Correct	187 ms	33752 KB	Output is correct
26	Correct	429 ms	175804 KB	Output is correct
27	Correct	503 ms	97516 KB	Output is correct
28	Correct	691 ms	82644 KB	Output is correct
29	Correct	664 ms	80168 KB	Output is correct
30	Correct	610 ms	90880 KB	Output is correct
31	Correct	624 ms	25836 KB	Output is correct
32	Correct	449 ms	78432 KB	Output is correct