oj.uz

Submission #754246

# Submission time Handle Problem Language Result Execution time Memory
754246 2023-06-07T10:23:27 Z hariaakas646 Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 806 ms 109896 KB 
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define scld(t) scanf("%ld", &t)
#define sclld(t) scanf("%lld", &t)
#define scc(t) scanf("%c", &t)
#define scs(t) scanf("%s", t)
#define scf(t) scanf("%f", &t)
#define sclf(t) scanf("%lf", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long int li;
typedef unsigned long int uli;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;

int main()
{
    int h, w;
    cin >> h >> w;
    vector<string> vec(h);

    frange(i, h) cin >> vec[i];

    deque<pii> dq;
    vector<vb> vis(h, vb(w));

    vvi dist(h, vi(w, 0));
    dq.pb({0, 0});
    dist[0][0] = 1;
    vii pos;
    pos.pb({0, 1});
    // pos.pb({0, -1});
    pos.pb({1, 0});
    // pos.pb({-1, 0});
    int ans = 1;
    while (dq.size())
    {
        auto p = dq.front();
        dq.pop_front();
        if (vis[p.f][p.s])
            continue;
        vis[p.f][p.s] = true;
        ans = max(ans, dist[p.f][p.s]);
        for (auto e : pos)
        {
            if (0 <= p.f + e.f && p.f + e.f < h && 0 <= p.s + e.s && p.s + e.s < w && vec[p.f + e.f][p.s + e.s] != '.')
            {
                int w = 0;
                if (vec[p.f][p.s] != vec[p.f + e.f][p.s + e.s])
                {
                    w = 1;
                }
                if (dist[p.f + e.f][p.s + e.s] == 0)
                {
                    dist[p.f + e.f][p.s + e.s] = dist[p.f][p.s] + w;
                    if (w)
                        dq.pb({p.f + e.f, p.s + e.s});
                    else
                        dq.push_front({p.f + e.f, p.s + e.s});
                }
            }
        }
    }
    printf("%d", ans);
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 2004 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 304 KB Output isn't correct
4 Incorrect 8 ms 1336 KB Output isn't correct
5 Incorrect 3 ms 824 KB Output isn't correct
6 Incorrect 1 ms 300 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 3 ms 724 KB Output isn't correct
11 Incorrect 3 ms 468 KB Output isn't correct
12 Incorrect 6 ms 852 KB Output isn't correct
13 Incorrect 3 ms 852 KB Output isn't correct
14 Incorrect 3 ms 824 KB Output isn't correct
15 Incorrect 10 ms 2104 KB Output isn't correct
16 Incorrect 14 ms 2052 KB Output isn't correct
17 Incorrect 10 ms 2004 KB Output isn't correct
18 Incorrect 7 ms 1364 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 980 KB Output isn't correct
2 Incorrect 48 ms 10572 KB Output isn't correct
3 Incorrect 374 ms 106528 KB Output isn't correct
4 Incorrect 106 ms 26408 KB Output isn't correct
5 Incorrect 199 ms 57076 KB Output isn't correct
6 Incorrect 806 ms 107724 KB Output isn't correct
7 Incorrect 3 ms 1108 KB Output isn't correct
8 Incorrect 3 ms 980 KB Output isn't correct
9 Incorrect 3 ms 624 KB Output isn't correct
10 Incorrect 2 ms 444 KB Output isn't correct
11 Incorrect 3 ms 980 KB Output isn't correct
12 Incorrect 1 ms 468 KB Output isn't correct
13 Incorrect 46 ms 10572 KB Output isn't correct
14 Incorrect 27 ms 6664 KB Output isn't correct
15 Incorrect 23 ms 7244 KB Output isn't correct
16 Incorrect 19 ms 4324 KB Output isn't correct
17 Incorrect 119 ms 28460 KB Output isn't correct
18 Incorrect 90 ms 28108 KB Output isn't correct
19 Incorrect 100 ms 26440 KB Output isn't correct
20 Incorrect 77 ms 24340 KB Output isn't correct
21 Incorrect 204 ms 58972 KB Output isn't correct
22 Incorrect 200 ms 57040 KB Output isn't correct
23 Incorrect 224 ms 48840 KB Output isn't correct
24 Incorrect 206 ms 58024 KB Output isn't correct
25 Incorrect 357 ms 106188 KB Output isn't correct
26 Correct 505 ms 71540 KB Output is correct
27 Incorrect 688 ms 109116 KB Output isn't correct
28 Incorrect 786 ms 109104 KB Output isn't correct
29 Incorrect 783 ms 109896 KB Output isn't correct
30 Incorrect 726 ms 107744 KB Output isn't correct
31 Incorrect 590 ms 64176 KB Output isn't correct
32 Incorrect 585 ms 108108 KB Output isn't correct