oj.uz

Submission #931377

# Submission time Handle Problem Language Result Execution time Memory
931377 2024-02-21T16:51:19 Z sofija6 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1132 ms 121764 KB 
#include <bits/stdc++.h>
#define ll int
#define MAXN 4001
using namespace std;
char c[MAXN][MAXN];
ll dist[MAXN][MAXN];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll h,w;
    cin >> h >> w;
    for (ll i=1;i<=h;i++)
    {
        for (ll j=1;j<=w;j++)
            cin >> c[i][j];
    }
    deque<pair<ll,ll> > q;
    q.push_back({1,1});
    dist[1][1]=1;
    ll ans=0;
    while (!q.empty())
    {
        ll i=q.front().first,j=q.front().second;
        q.pop_front();
        ans=max(ans,dist[i][j]);
        vector<pair<ll,ll> > same,diff;
        for (ll x=-1;x<2;x++)
        {
            for (ll y=-1;y<2;y++)
            {
                if (abs(x)+abs(y)==1 && (c[i+x][j+y]=='R' || c[i+x][j+y]=='F') && !dist[i+x][j+y])
                {
                    dist[i+x][j+y]=dist[i][j]+(c[i+x][j+y]!=c[i][j]);
                    if (c[i+x][j+y]!=c[i][j])
                        diff.push_back({i+x,j+y});
                    else
                        same.push_back({i+x,j+y});
                }
            }
        }
        for (auto x : same)
            q.push_front(x);
        for (auto x : diff)
            q.push_back(x);
    }
    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 7504 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 11 ms 7288 KB Output is correct
5 Correct 4 ms 3928 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 3 ms 3420 KB Output is correct
11 Correct 3 ms 3420 KB Output is correct
12 Correct 8 ms 4184 KB Output is correct
13 Correct 4 ms 3932 KB Output is correct
14 Correct 3 ms 3932 KB Output is correct
15 Correct 19 ms 7260 KB Output is correct
16 Correct 21 ms 7464 KB Output is correct
17 Correct 12 ms 7256 KB Output is correct
18 Correct 11 ms 7260 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 32344 KB Output is correct
2 Correct 70 ms 14832 KB Output is correct
3 Correct 447 ms 58536 KB Output is correct
4 Correct 95 ms 31824 KB Output is correct
5 Correct 300 ms 47040 KB Output is correct
6 Correct 1102 ms 93640 KB Output is correct
7 Correct 9 ms 32860 KB Output is correct
8 Correct 9 ms 32348 KB Output is correct
9 Correct 3 ms 2716 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 9 ms 32516 KB Output is correct
12 Correct 2 ms 3164 KB Output is correct
13 Correct 66 ms 14920 KB Output is correct
14 Correct 39 ms 12256 KB Output is correct
15 Correct 30 ms 14296 KB Output is correct
16 Correct 34 ms 7508 KB Output is correct
17 Correct 170 ms 27152 KB Output is correct
18 Correct 115 ms 34132 KB Output is correct
19 Correct 90 ms 31828 KB Output is correct
20 Correct 92 ms 23632 KB Output is correct
21 Correct 238 ms 45780 KB Output is correct
22 Correct 296 ms 47184 KB Output is correct
23 Correct 317 ms 38740 KB Output is correct
24 Correct 246 ms 43212 KB Output is correct
25 Correct 521 ms 78724 KB Output is correct
26 Correct 727 ms 121764 KB Output is correct
27 Correct 982 ms 119556 KB Output is correct
28 Correct 1114 ms 93728 KB Output is correct
29 Correct 1104 ms 91328 KB Output is correct
30 Correct 1132 ms 95556 KB Output is correct
31 Correct 875 ms 65300 KB Output is correct
32 Correct 851 ms 100956 KB Output is correct