oj.uz

Submission #590119

# Submission time Handle Problem Language Result Execution time Memory
590119 2022-07-05T14:35:18 Z Minhho Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 747 ms 241592 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);
    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] && min(a[i][j], 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 6696 KB Output isn't correct
2 Incorrect 0 ms 456 KB Output isn't correct
3 Incorrect 1 ms 712 KB Output isn't correct
4 Correct 8 ms 5844 KB Output is correct
5 Incorrect 5 ms 3876 KB Output isn't correct
6 Incorrect 0 ms 468 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 1 ms 1236 KB Output isn't correct
10 Incorrect 4 ms 3284 KB Output isn't correct
11 Correct 3 ms 2388 KB Output is correct
12 Incorrect 10 ms 3584 KB Output isn't correct
13 Incorrect 5 ms 3780 KB Output isn't correct
14 Incorrect 5 ms 3788 KB Output isn't correct
15 Incorrect 16 ms 7608 KB Output isn't correct
16 Incorrect 16 ms 6620 KB Output isn't correct
17 Incorrect 16 ms 7644 KB Output isn't correct
18 Correct 8 ms 5964 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 31828 KB Output isn't correct
2 Incorrect 88 ms 33096 KB Output isn't correct
3 Incorrect 672 ms 239112 KB Output isn't correct
4 Incorrect 181 ms 70896 KB Output isn't correct
5 Incorrect 321 ms 157712 KB Output isn't correct
6 Correct 717 ms 162224 KB Output is correct
7 Incorrect 15 ms 33108 KB Output isn't correct
8 Incorrect 15 ms 31784 KB Output isn't correct
9 Incorrect 3 ms 980 KB Output isn't correct
10 Incorrect 1 ms 732 KB Output isn't correct
11 Incorrect 15 ms 32536 KB Output isn't correct
12 Incorrect 2 ms 1884 KB Output isn't correct
13 Incorrect 81 ms 33100 KB Output isn't correct
14 Incorrect 47 ms 20684 KB Output isn't correct
15 Incorrect 48 ms 23372 KB Output isn't correct
16 Incorrect 36 ms 12500 KB Output isn't correct
17 Incorrect 196 ms 76008 KB Output isn't correct
18 Incorrect 170 ms 76540 KB Output isn't correct
19 Incorrect 177 ms 70896 KB Output isn't correct
20 Incorrect 151 ms 65600 KB Output isn't correct
21 Incorrect 398 ms 163756 KB Output isn't correct
22 Incorrect 326 ms 157808 KB Output isn't correct
23 Incorrect 378 ms 131636 KB Output isn't correct
24 Incorrect 354 ms 164296 KB Output isn't correct
25 Incorrect 653 ms 241592 KB Output isn't correct
26 Correct 416 ms 196352 KB Output is correct
27 Correct 581 ms 192656 KB Output is correct
28 Correct 747 ms 162464 KB Output is correct
29 Correct 709 ms 158688 KB Output is correct
30 Correct 646 ms 167244 KB Output is correct
31 Incorrect 685 ms 112444 KB Output isn't correct
32 Incorrect 590 ms 217184 KB Output isn't correct