oj.uz

Submission #379409

# Submission time Handle Problem Language Result Execution time Memory
379409 2021-03-18T07:14:37 Z LittleCube Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1927 ms 131068 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#pragma pack(0)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define MOD 1000000007
#define MOD2 998244353
#define _INFINITY 9223372036854775807
#define fast ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int n, m, r, f, dis[4005][4005], ans = 1;
char mp[4005][4005];
signed main()
{
    auto add = [](pii p1, pii p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); };
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];

    if (mp[1][1] == '.')
    {
        cout << 1;
        return 0;
    }

    deque<pii> dq;
    dq.push_front(pii{1, 1});
    dis[1][1] = 1;
    while (!dq.empty())
    {
        pii x = dq.front();
        dq.pop_front();
        for (pii i : vector<pii>{{0, 1}, {0, -1}, {1, 0}, {-1, 0}})
        {
            pii cur = add(i, x);
            if ((mp[cur.F][cur.S] != 'R' && mp[cur.F][cur.S] != 'F') || dis[cur.F][cur.S] != 0)
                continue;
            if (mp[cur.F][cur.S] == mp[x.F][x.S])
            {
                dq.push_front(cur);
                dis[cur.F][cur.S] = dis[x.F][x.S];
            }
            else if (mp[cur.F][cur.S] != mp[x.F][x.S])
            {
                dq.push_back(cur);
                dis[cur.F][cur.S] = dis[x.F][x.S] + 1;
                ans = max(ans, dis[cur.F][cur.S]);
            }
        }
    }
    cout << ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5628 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 20 ms 5228 KB Output is correct
5 Correct 9 ms 2924 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 8 ms 2540 KB Output is correct
11 Correct 6 ms 2156 KB Output is correct
12 Correct 13 ms 3052 KB Output is correct
13 Correct 9 ms 2924 KB Output is correct
14 Correct 9 ms 2924 KB Output is correct
15 Correct 32 ms 5356 KB Output is correct
16 Correct 34 ms 5484 KB Output is correct
17 Correct 26 ms 5228 KB Output is correct
18 Correct 20 ms 5228 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 30848 KB Output is correct
2 Correct 150 ms 15084 KB Output is correct
3 Correct 1183 ms 73228 KB Output is correct
4 Correct 322 ms 32820 KB Output is correct
5 Correct 698 ms 53336 KB Output is correct
6 Correct 1882 ms 107028 KB Output is correct
7 Correct 24 ms 32364 KB Output is correct
8 Correct 23 ms 30828 KB Output is correct
9 Correct 6 ms 748 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 23 ms 31596 KB Output is correct
12 Correct 3 ms 1644 KB Output is correct
13 Correct 157 ms 15084 KB Output is correct
14 Correct 87 ms 10552 KB Output is correct
15 Correct 85 ms 13164 KB Output is correct
16 Correct 66 ms 5868 KB Output is correct
17 Correct 379 ms 29036 KB Output is correct
18 Correct 330 ms 35692 KB Output is correct
19 Correct 297 ms 32876 KB Output is correct
20 Correct 269 ms 25580 KB Output is correct
21 Correct 706 ms 52588 KB Output is correct
22 Correct 697 ms 53412 KB Output is correct
23 Correct 733 ms 43860 KB Output is correct
24 Correct 674 ms 50028 KB Output is correct
25 Correct 1424 ms 93932 KB Output is correct
26 Correct 1762 ms 131068 KB Output is correct
27 Correct 1912 ms 112564 KB Output is correct
28 Correct 1927 ms 107300 KB Output is correct
29 Correct 1873 ms 105416 KB Output is correct
30 Correct 1866 ms 109664 KB Output is correct
31 Correct 1439 ms 73452 KB Output is correct
32 Correct 1817 ms 110304 KB Output is correct