oj.uz

Submission #931375

# Submission time Handle Problem Language Result Execution time Memory
931375 2024-02-21T16:50:05 Z sofija6 Tracks in the Snow (BOI13_tracks) C++14
29.5833 / 100
 1209 ms 94596 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];
    }
    queue<pair<ll,ll> > q;
    q.push({1,1});
    dist[1][1]=1;
    ll ans=0;
    while (!q.empty())
    {
        ll i=q.front().first,j=q.front().second;
        q.pop();
        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(x);
        for (auto x : diff)
            q.push(x);
    }
    cout << ans;
    return 0;
}

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 7512 KB Output isn't correct
2 Correct 1 ms 2392 KB Output is correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Incorrect 12 ms 7140 KB Output isn't correct
5 Incorrect 4 ms 3932 KB Output isn't correct
6 Correct 1 ms 2396 KB Output is correct
7 Incorrect 1 ms 2652 KB Output isn't correct
8 Incorrect 1 ms 2656 KB Output isn't correct
9 Incorrect 1 ms 2908 KB Output isn't correct
10 Incorrect 4 ms 3676 KB Output isn't correct
11 Incorrect 3 ms 3420 KB Output isn't correct
12 Incorrect 8 ms 3932 KB Output isn't correct
13 Incorrect 5 ms 4060 KB Output isn't correct
14 Incorrect 4 ms 3940 KB Output isn't correct
15 Incorrect 19 ms 7360 KB Output isn't correct
16 Incorrect 21 ms 7512 KB Output isn't correct
17 Incorrect 13 ms 7516 KB Output isn't correct
18 Incorrect 12 ms 7260 KB Output isn't correct

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 32348 KB Output is correct
2 Incorrect 67 ms 16356 KB Output isn't correct
3 Incorrect 425 ms 70720 KB Output isn't correct
4 Incorrect 96 ms 35068 KB Output isn't correct
5 Correct 266 ms 54340 KB Output is correct
6 Incorrect 1209 ms 91160 KB Output isn't correct
7 Correct 10 ms 32860 KB Output is correct
8 Correct 11 ms 32348 KB Output is correct
9 Incorrect 3 ms 2652 KB Output isn't correct
10 Correct 1 ms 2396 KB Output is correct
11 Incorrect 10 ms 32604 KB Output isn't correct
12 Correct 2 ms 3164 KB Output is correct
13 Incorrect 77 ms 16596 KB Output isn't correct
14 Incorrect 40 ms 13140 KB Output isn't correct
15 Correct 30 ms 15440 KB Output is correct
16 Incorrect 34 ms 8276 KB Output isn't correct
17 Incorrect 170 ms 30808 KB Output isn't correct
18 Correct 116 ms 37724 KB Output is correct
19 Incorrect 93 ms 35156 KB Output isn't correct
20 Incorrect 93 ms 26428 KB Output isn't correct
21 Incorrect 229 ms 53332 KB Output isn't correct
22 Correct 261 ms 54208 KB Output is correct
23 Incorrect 330 ms 45004 KB Output isn't correct
24 Correct 223 ms 50100 KB Output is correct
25 Correct 530 ms 91056 KB Output is correct
26 Correct 769 ms 83776 KB Output is correct
27 Incorrect 1045 ms 94596 KB Output isn't correct
28 Incorrect 1156 ms 78676 KB Output isn't correct
29 Incorrect 1157 ms 78616 KB Output isn't correct
30 Incorrect 1160 ms 78132 KB Output isn't correct
31 Incorrect 960 ms 64932 KB Output isn't correct
32 Incorrect 952 ms 94336 KB Output isn't correct