oj.uz

Submission #590128

# Submission time Handle Problem Language Result Execution time Memory
590128 2022-07-05T14:40:26 Z Minhho Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 856 ms 210544 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;}

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] && a[ci][cj] != -1;
                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++) ans = max(ans, d[i][j]);
    cout<<ans;
}

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 6484 KB Output isn't correct
2 Incorrect 0 ms 468 KB Output isn't correct
3 Incorrect 1 ms 724 KB Output isn't correct
4 Correct 9 ms 5844 KB Output is correct
5 Incorrect 6 ms 3412 KB Output isn't correct
6 Incorrect 0 ms 460 KB Output isn't correct
7 Incorrect 1 ms 724 KB Output isn't correct
8 Correct 1 ms 852 KB Output is correct
9 Incorrect 2 ms 1236 KB Output isn't correct
10 Incorrect 4 ms 3152 KB Output isn't correct
11 Correct 3 ms 2388 KB Output is correct
12 Incorrect 9 ms 3412 KB Output isn't correct
13 Incorrect 6 ms 3412 KB Output isn't correct
14 Incorrect 6 ms 3540 KB Output isn't correct
15 Incorrect 16 ms 7256 KB Output isn't correct
16 Incorrect 16 ms 6484 KB Output isn't correct
17 Incorrect 16 ms 6356 KB Output isn't correct
18 Correct 9 ms 5844 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 31700 KB Output isn't correct
2 Incorrect 73 ms 29392 KB Output isn't correct
3 Incorrect 637 ms 210544 KB Output isn't correct
4 Incorrect 212 ms 47280 KB Output isn't correct
5 Incorrect 331 ms 150368 KB Output isn't correct
6 Correct 756 ms 148140 KB Output is correct
7 Incorrect 16 ms 33108 KB Output isn't correct
8 Incorrect 17 ms 31700 KB Output isn't correct
9 Incorrect 4 ms 980 KB Output isn't correct
10 Incorrect 2 ms 724 KB Output isn't correct
11 Incorrect 16 ms 32596 KB Output isn't correct
12 Incorrect 2 ms 1876 KB Output isn't correct
13 Incorrect 78 ms 29488 KB Output isn't correct
14 Incorrect 45 ms 19020 KB Output isn't correct
15 Incorrect 63 ms 21508 KB Output isn't correct
16 Incorrect 32 ms 11460 KB Output isn't correct
17 Incorrect 182 ms 64232 KB Output isn't correct
18 Incorrect 225 ms 66676 KB Output isn't correct
19 Incorrect 180 ms 47164 KB Output isn't correct
20 Incorrect 147 ms 60588 KB Output isn't correct
21 Incorrect 406 ms 154940 KB Output isn't correct
22 Incorrect 323 ms 150364 KB Output isn't correct
23 Incorrect 355 ms 108256 KB Output isn't correct
24 Incorrect 339 ms 137268 KB Output isn't correct
25 Incorrect 856 ms 182848 KB Output isn't correct
26 Correct 453 ms 185768 KB Output is correct
27 Correct 616 ms 178396 KB Output is correct
28 Correct 818 ms 147940 KB Output is correct
29 Correct 812 ms 144476 KB Output is correct
30 Correct 678 ms 153120 KB Output is correct
31 Incorrect 704 ms 102940 KB Output isn't correct
32 Incorrect 626 ms 164040 KB Output isn't correct