oj.uz

Submission #1000424

# Submission time Handle Problem Language Result Execution time Memory
1000424 2024-06-17T13:48:20 Z AlgorithmWarrior Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1014 ms 132196 KB 
#include <bits/stdc++.h>
#define MAX 4005
#define PII pair<int,int>

using namespace std;

char mat[MAX][MAX];
int bfs[MAX][MAX];
int dl[]={-1,0,1,0};
int dc[]={0,1,0,-1};

int main()
{
    int n,m;
    cin>>n>>m;
    int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {
            cin>>mat[i][j];
            bfs[i][j]=INT_MAX;
        }
    bfs[1][1]=1;
    deque<PII>deq;
    deq.push_front({1,1});
    while(!deq.empty())
    {
        PII nou=deq.front();
        int l=nou.first;
        int c=nou.second;
        deq.pop_front();
        for(i=0;i<4;++i)
        {
            int lnou=l+dl[i];
            int cnou=c+dc[i];
            int pret=bfs[l][c]+(mat[l][c]!=mat[lnou][cnou]);
            if(isalpha(mat[lnou][cnou]) && pret<bfs[lnou][cnou])
            {
                bfs[lnou][cnou]=pret;
                if(mat[l][c]==mat[lnou][cnou])
                    deq.push_front({lnou,cnou});
                else
                    deq.push_back({lnou,cnou});
            }
        }
    }
    int answer=-1;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(isalpha(mat[i][j]))
                answer=max(answer,bfs[i][j]);
    cout<<answer;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12892 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 9 ms 13148 KB Output is correct
5 Correct 5 ms 10792 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 8 ms 10844 KB Output is correct
13 Correct 5 ms 10844 KB Output is correct
14 Correct 4 ms 10824 KB Output is correct
15 Correct 18 ms 13036 KB Output is correct
16 Correct 16 ms 12892 KB Output is correct
17 Correct 14 ms 13052 KB Output is correct
18 Correct 10 ms 13084 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 51752 KB Output is correct
2 Correct 70 ms 28572 KB Output is correct
3 Correct 599 ms 94388 KB Output is correct
4 Correct 149 ms 41296 KB Output is correct
5 Correct 352 ms 68984 KB Output is correct
6 Correct 954 ms 109212 KB Output is correct
7 Correct 11 ms 51292 KB Output is correct
8 Correct 13 ms 50208 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 12 ms 46500 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 76 ms 28564 KB Output is correct
14 Correct 40 ms 21848 KB Output is correct
15 Correct 39 ms 23896 KB Output is correct
16 Correct 32 ms 11424 KB Output is correct
17 Correct 183 ms 45396 KB Output is correct
18 Correct 174 ms 43856 KB Output is correct
19 Correct 151 ms 41812 KB Output is correct
20 Correct 131 ms 40788 KB Output is correct
21 Correct 364 ms 71244 KB Output is correct
22 Correct 363 ms 68948 KB Output is correct
23 Correct 401 ms 57932 KB Output is correct
24 Correct 412 ms 70992 KB Output is correct
25 Correct 646 ms 94280 KB Output is correct
26 Correct 669 ms 132196 KB Output is correct
27 Correct 854 ms 123652 KB Output is correct
28 Correct 963 ms 108980 KB Output is correct
29 Correct 1014 ms 105276 KB Output is correct
30 Correct 921 ms 113364 KB Output is correct
31 Correct 632 ms 74440 KB Output is correct
32 Correct 910 ms 114024 KB Output is correct