oj.uz

Submission #590138

# Submission time Handle Problem Language Result Execution time Memory
590138 2022-07-05T14:47:41 Z Minhho Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 815 ms 186076 KB 
#define taskname "1"
#include <bits/stdc++.h>
#define iii tuple<int,int,int>

using namespace std;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}, maxn = 4010;
int a[maxn][maxn], d[maxn][maxn], w, h;
deque<iii> dq;

bool val(int i, int j) {return min(i, j) >= 1 && i <= w && j <= h && a[i][j] != -1;}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //freopen("1.inp", "r", stdin);
    cin>>w>>h;
    char c;
    for (int i=1; i<=w; i++) for (int j=1; j<=h; j++) cin>>c, a[i][j] = c != '.' ? c : -1, d[i][j] = maxn * maxn;
    d[1][1] = 1;
    dq.emplace_back(1, 1, 1);
    while (!dq.empty())
    {
        auto [i, j, dij] = dq.front(); dq.pop_front();
        if (dij != d[i][j]) continue;
        for (int k=0; k<4; k++)
        {
            int ci = i + dx[k], cj = j + dy[k];
            if (val(ci, cj))
            {
                int wt = a[i][j] != a[ci][cj];
                if (dij + wt < d[ci][cj])
                {
                    d[ci][cj] = dij + wt;
                    if (wt) dq.emplace_back(ci, cj, dij+wt);
                    else dq.emplace_front(ci, cj, dij+wt);
                }
            }
        }
    }
    int ans = -1;
    for (int i=1; i<=w; i++) for (int j=1; j<=h; j++) if (a[i][j] != -1) ans = max(ans, d[i][j]);
    cout<<ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6484 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 9 ms 5956 KB Output is correct
5 Correct 4 ms 3284 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 3 ms 2900 KB Output is correct
11 Correct 3 ms 2388 KB Output is correct
12 Correct 6 ms 3416 KB Output is correct
13 Correct 4 ms 3284 KB Output is correct
14 Correct 4 ms 3284 KB Output is correct
15 Correct 13 ms 6484 KB Output is correct
16 Correct 15 ms 6492 KB Output is correct
17 Correct 11 ms 6232 KB Output is correct
18 Correct 8 ms 5976 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31444 KB Output is correct
2 Correct 54 ms 23644 KB Output is correct
3 Correct 366 ms 127552 KB Output is correct
4 Correct 123 ms 46288 KB Output is correct
5 Correct 249 ms 96040 KB Output is correct
6 Correct 759 ms 148272 KB Output is correct
7 Correct 14 ms 32816 KB Output is correct
8 Correct 15 ms 31444 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 15 ms 32308 KB Output is correct
12 Correct 1 ms 1640 KB Output is correct
13 Correct 60 ms 23424 KB Output is correct
14 Correct 37 ms 15480 KB Output is correct
15 Correct 42 ms 16832 KB Output is correct
16 Correct 28 ms 9200 KB Output is correct
17 Correct 136 ms 49848 KB Output is correct
18 Correct 113 ms 49224 KB Output is correct
19 Correct 111 ms 46388 KB Output is correct
20 Correct 90 ms 42900 KB Output is correct
21 Correct 250 ms 99436 KB Output is correct
22 Correct 237 ms 96336 KB Output is correct
23 Correct 299 ms 80648 KB Output is correct
24 Correct 221 ms 98252 KB Output is correct
25 Correct 543 ms 127664 KB Output is correct
26 Correct 468 ms 186076 KB Output is correct
27 Correct 629 ms 178688 KB Output is correct
28 Correct 738 ms 148356 KB Output is correct
29 Correct 815 ms 144656 KB Output is correct
30 Correct 727 ms 153484 KB Output is correct
31 Correct 589 ms 103144 KB Output is correct
32 Correct 581 ms 163572 KB Output is correct