oj.uz

Submission #754137

# Submission time Handle Problem Language Result Execution time Memory
754137 2023-06-06T23:49:34 Z ivaziva Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1422 ms 252240 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 4010

long long n;
long long m;
char matrica[MAXN][MAXN];
long long dist[MAXN][MAXN];
deque<pair<long long,long long>> bfsq;
long long sx[5];
long long sy[5];
long long ans;

bool unutar(long long a,long long b)
{
    if (a>=1 and a<=n and b>=1 and b<=m and matrica[a][b]!='.') return true;
    else return false;
}

void bfs(long long x,long long y)
{
    for (long long i=0;i<MAXN;i++)
    {
        for (long long j=0;j<MAXN;j++) dist[i][j]=LLONG_MAX;
    }
    dist[x][y]=0;
    bfsq.push_front({x,y});
    ans=0;
    while (bfsq.empty()==false)
    {
        long long nodex=bfsq.front().first;
        long long nodey=bfsq.front().second;
        bfsq.pop_front();
        ans=max(ans,dist[nodex][nodey]);
        for (long long i=1;i<=4;i++)
        {
            long long sledx=nodex+sx[i];
            long long sledy=nodey+sy[i];
            if (unutar(sledx,sledy) and dist[sledx][sledy]==LLONG_MAX)
            {
                if (matrica[nodex][nodey]==matrica[sledx][sledy])
                {
                    dist[sledx][sledy]=dist[nodex][nodey];
                    bfsq.push_front({sledx,sledy});
                }
                else
                {
                    dist[sledx][sledy]=dist[nodex][nodey]+1;
                    bfsq.push_back({sledx,sledy});
                }
            }
        }
    }
}

int main()
{
    sx[1]=1,sy[1]=0;
    sx[2]=-1,sy[2]=0;
    sx[3]=0,sy[3]=1;
    sx[4]=0,sy[4]=-1;
    cin>>n>>m;
    for (long long i=1;i<=n;i++)
    {
        for (long long j=1;j<=m;j++) cin>>matrica[i][j];
    }
    bfs(1,0);
    cout<<ans<<endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 128360 KB Output is correct
2 Correct 53 ms 126156 KB Output is correct
3 Correct 57 ms 126244 KB Output is correct
4 Correct 60 ms 128576 KB Output is correct
5 Correct 59 ms 127352 KB Output is correct
6 Correct 49 ms 126240 KB Output is correct
7 Correct 50 ms 126284 KB Output is correct
8 Correct 49 ms 126368 KB Output is correct
9 Correct 50 ms 126540 KB Output is correct
10 Correct 53 ms 127164 KB Output is correct
11 Correct 54 ms 127224 KB Output is correct
12 Correct 59 ms 127436 KB Output is correct
13 Correct 55 ms 127392 KB Output is correct
14 Correct 57 ms 127308 KB Output is correct
15 Correct 75 ms 128328 KB Output is correct
16 Correct 71 ms 128348 KB Output is correct
17 Correct 72 ms 128292 KB Output is correct
18 Correct 61 ms 128660 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 141204 KB Output is correct
2 Correct 158 ms 132608 KB Output is correct
3 Correct 1006 ms 154960 KB Output is correct
4 Correct 290 ms 137164 KB Output is correct
5 Correct 588 ms 146724 KB Output is correct
6 Correct 1409 ms 182232 KB Output is correct
7 Correct 66 ms 141852 KB Output is correct
8 Correct 62 ms 141092 KB Output is correct
9 Correct 60 ms 126264 KB Output is correct
10 Correct 51 ms 126240 KB Output is correct
11 Correct 60 ms 141588 KB Output is correct
12 Correct 52 ms 126700 KB Output is correct
13 Correct 163 ms 132512 KB Output is correct
14 Correct 111 ms 130528 KB Output is correct
15 Correct 115 ms 131000 KB Output is correct
16 Correct 98 ms 128280 KB Output is correct
17 Correct 336 ms 138092 KB Output is correct
18 Correct 337 ms 137920 KB Output is correct
19 Correct 285 ms 137300 KB Output is correct
20 Correct 257 ms 136400 KB Output is correct
21 Correct 619 ms 147536 KB Output is correct
22 Correct 615 ms 146672 KB Output is correct
23 Correct 625 ms 143688 KB Output is correct
24 Correct 597 ms 147268 KB Output is correct
25 Correct 1214 ms 154816 KB Output is correct
26 Correct 1038 ms 252240 KB Output is correct
27 Correct 1343 ms 208412 KB Output is correct
28 Correct 1399 ms 182412 KB Output is correct
29 Correct 1422 ms 178472 KB Output is correct
30 Correct 1335 ms 190104 KB Output is correct
31 Correct 1006 ms 149644 KB Output is correct
32 Correct 1280 ms 186048 KB Output is correct