Submission #990784

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

tracks

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int H, W;
vector<string> meadow;
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;
    meadow.resize(H);

    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	3928 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	6 ms	4444 KB	Output is correct
5	Correct	2 ms	2140 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	464 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	0 ms	860 KB	Output is correct
10	Correct	2 ms	1664 KB	Output is correct
11	Correct	2 ms	1880 KB	Output is correct
12	Correct	4 ms	2140 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	3864 KB	Output is correct
16	Correct	9 ms	3936 KB	Output is correct
17	Correct	6 ms	3672 KB	Output is correct
18	Correct	6 ms	4440 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	16216 KB	Output is correct
2	Correct	30 ms	11544 KB	Output is correct
3	Correct	160 ms	68772 KB	Output is correct
4	Correct	50 ms	27984 KB	Output is correct
5	Correct	172 ms	47952 KB	Output is correct
6	Correct	533 ms	147172 KB	Output is correct
7	Correct	8 ms	16984 KB	Output is correct
8	Correct	7 ms	16220 KB	Output is correct
9	Correct	2 ms	1116 KB	Output is correct
10	Correct	1 ms	860 KB	Output is correct
11	Correct	7 ms	16808 KB	Output is correct
12	Correct	1 ms	1112 KB	Output is correct
13	Correct	30 ms	11604 KB	Output is correct
14	Correct	17 ms	8024 KB	Output is correct
15	Correct	15 ms	10332 KB	Output is correct
16	Correct	14 ms	4956 KB	Output is correct
17	Correct	78 ms	23924 KB	Output is correct
18	Correct	50 ms	30800 KB	Output is correct
19	Correct	47 ms	28240 KB	Output is correct
20	Correct	39 ms	21328 KB	Output is correct
21	Correct	95 ms	46932 KB	Output is correct
22	Correct	137 ms	47956 KB	Output is correct
23	Correct	162 ms	39508 KB	Output is correct
24	Correct	100 ms	43596 KB	Output is correct
25	Correct	226 ms	89688 KB	Output is correct
26	Runtime error	674 ms	1048576 KB	Execution killed with signal 9
27	Correct	734 ms	383568 KB	Output is correct
28	Correct	552 ms	138976 KB	Output is correct
29	Correct	502 ms	129508 KB	Output is correct
30	Correct	579 ms	188220 KB	Output is correct
31	Correct	356 ms	62804 KB	Output is correct
32	Correct	701 ms	409428 KB	Output is correct