oj.uz

Submission #807468

# Submission time Handle Problem Language Result Execution time Memory
807468 2023-08-04T17:50:55 Z gtm7 Tracks in the Snow (BOI13_tracks) C++17
82.5 / 100
 2000 ms 178312 KB 
#include <bits/stdc++.h>
using namespace std;

int a[4000][4000];
bool visited[4000][4000]{false};
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    int h, w;
    cin >> h >> w;
    char ch;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> ch;
            if (ch == 'F')
                a[i][j] = 1;
            else if (ch == 'R')
                a[i][j] = 2;
            else
                a[i][j] = 3;
        }
    }
    int ans = 1;
    set<vector<int>> q;
    vector<int> s;
    int ii, jj;
    q.insert({1, 0, 0});
    visited[0][0] = true;
    while (!q.empty())
    {
        s = *q.begin();
        q.erase(q.begin());
        for (int i = 0; i < 4; i++)
        {
            ii = s[1] + dx[i];
            jj = s[2] + dy[i];
            if (ii >= 0 && ii < h && jj >= 0 && jj < w && !visited[ii][jj] && a[ii][jj] != 3)
            {
                visited[ii][jj] = true;
                if (a[ii][jj] == a[s[1]][s[2]])
                {
                    q.insert({s[0], ii, jj});
                }
                else
                {
                    ans = max(ans, s[0] + 1);
                    q.insert({s[0] + 1, ii, jj});
                }
            }
        }
    }
    cout << ans << endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 6052 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 692 KB Output is correct
4 Correct 38 ms 6480 KB Output is correct
5 Correct 8 ms 2952 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 8 ms 2516 KB Output is correct
11 Correct 10 ms 2516 KB Output is correct
12 Correct 20 ms 3384 KB Output is correct
13 Correct 8 ms 3020 KB Output is correct
14 Correct 8 ms 2900 KB Output is correct
15 Correct 45 ms 5772 KB Output is correct
16 Correct 58 ms 6080 KB Output is correct
17 Correct 33 ms 5616 KB Output is correct
18 Correct 41 ms 6472 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31172 KB Output is correct
2 Correct 181 ms 18032 KB Output is correct
3 Correct 1000 ms 94204 KB Output is correct
4 Correct 251 ms 33504 KB Output is correct
5 Correct 613 ms 67812 KB Output is correct
6 Execution timed out 2070 ms 169376 KB Time limit exceeded
7 Correct 17 ms 32596 KB Output is correct
8 Correct 21 ms 31060 KB Output is correct
9 Correct 8 ms 852 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 15 ms 32040 KB Output is correct
12 Correct 2 ms 1600 KB Output is correct
13 Correct 192 ms 18040 KB Output is correct
14 Correct 128 ms 12088 KB Output is correct
15 Correct 63 ms 13072 KB Output is correct
16 Correct 89 ms 6792 KB Output is correct
17 Correct 473 ms 36400 KB Output is correct
18 Correct 296 ms 35856 KB Output is correct
19 Correct 281 ms 33496 KB Output is correct
20 Correct 230 ms 31000 KB Output is correct
21 Correct 653 ms 70072 KB Output is correct
22 Correct 651 ms 67812 KB Output is correct
23 Correct 957 ms 57220 KB Output is correct
24 Correct 564 ms 69396 KB Output is correct
25 Correct 1113 ms 94224 KB Output is correct
26 Execution timed out 2080 ms 76940 KB Time limit exceeded
27 Execution timed out 2058 ms 101452 KB Time limit exceeded
28 Execution timed out 2054 ms 169356 KB Time limit exceeded
29 Execution timed out 2072 ms 172460 KB Time limit exceeded
30 Execution timed out 2084 ms 178312 KB Time limit exceeded
31 Execution timed out 2072 ms 77648 KB Time limit exceeded
32 Execution timed out 2074 ms 101504 KB Time limit exceeded