Submission #990788

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
990788	2024-05-31T10:55:58 Z	kfhjad	Tracks in the Snow (BOI13_tracks)	C++17	97.8125 / 100	695 ms	1048576 KB

tracks

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int H, W;
string meadow[4000];
int val[4000][4000];
queue<pair<int, int>> q;

int switches;
char animal;
bool cnt;

void dfs(int row, int col)
{
    if (row < 0 || col < 0 || row == H || col == W || meadow[row][col] == '.')
        return;
    
    if (val[row][col] != 0 && cnt)
        return;

    cnt = true;

    if (animal != meadow[row][col])
    {
        q.push({row, col});
        val[row][col] = switches + 1;
        return;
    }

    val[row][col] = switches;

    dfs(row + 1, col);
    dfs(row - 1, col);
    dfs(row, col + 1);
    dfs(row, col - 1);
}

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    cin >> H >> W;

    for (auto& i : meadow)
        cin >> i;
    
    q.push({0, 0});
    val[0][0] = 1;

    while (!q.empty())
    {
        auto [row, col] = q.front();
        q.pop();

        switches = val[row][col];
        animal = meadow[row][col];
        cnt = false;
        dfs(row, col);
    }
    
    int ans = 0;

    for (int i = 0; i < H; ++i)
        for (int j = 0; j < W; ++j)
            ans = max(ans, val[i][j]);

    cout << ans << endl;

    return 0;
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	3676 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	6 ms	4444 KB	Output is correct
5	Correct	2 ms	1988 KB	Output is correct
6	Correct	0 ms	604 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	1 ms	860 KB	Output is correct
9	Correct	1 ms	856 KB	Output is correct
10	Correct	2 ms	1628 KB	Output is correct
11	Correct	2 ms	1884 KB	Output is correct
12	Correct	4 ms	2136 KB	Output is correct
13	Correct	2 ms	2140 KB	Output is correct
14	Correct	2 ms	2140 KB	Output is correct
15	Correct	7 ms	3676 KB	Output is correct
16	Correct	9 ms	3672 KB	Output is correct
17	Correct	6 ms	3676 KB	Output is correct
18	Correct	6 ms	4444 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	16220 KB	Output is correct
2	Correct	27 ms	10576 KB	Output is correct
3	Correct	147 ms	60500 KB	Output is correct
4	Correct	47 ms	26196 KB	Output is correct
5	Correct	143 ms	43408 KB	Output is correct
6	Correct	536 ms	138816 KB	Output is correct
7	Correct	8 ms	16984 KB	Output is correct
8	Correct	8 ms	16216 KB	Output is correct
9	Correct	1 ms	1116 KB	Output is correct
10	Correct	1 ms	860 KB	Output is correct
11	Correct	7 ms	16572 KB	Output is correct
12	Correct	1 ms	1112 KB	Output is correct
13	Correct	27 ms	10588 KB	Output is correct
14	Correct	15 ms	7260 KB	Output is correct
15	Correct	12 ms	9480 KB	Output is correct
16	Correct	13 ms	4696 KB	Output is correct
17	Correct	73 ms	21744 KB	Output is correct
18	Correct	53 ms	28496 KB	Output is correct
19	Correct	46 ms	26192 KB	Output is correct
20	Correct	38 ms	19384 KB	Output is correct
21	Correct	96 ms	42068 KB	Output is correct
22	Correct	136 ms	43400 KB	Output is correct
23	Correct	145 ms	35408 KB	Output is correct
24	Correct	100 ms	38992 KB	Output is correct
25	Correct	223 ms	81488 KB	Output is correct
26	Runtime error	648 ms	1048576 KB	Execution killed with signal 9
27	Correct	687 ms	383556 KB	Output is correct
28	Correct	523 ms	138764 KB	Output is correct
29	Correct	505 ms	129440 KB	Output is correct
30	Correct	559 ms	188388 KB	Output is correct
31	Correct	356 ms	62920 KB	Output is correct
32	Correct	695 ms	409428 KB	Output is correct