oj.uz

Submission #1000415

# Submission time Handle Problem Language Result Execution time Memory
1000415 2024-06-17T13:25:21 Z AlgorithmWarrior Tracks in the Snow (BOI13_tracks) C++14
78.125 / 100
 2000 ms 94812 KB 
#include <bits/stdc++.h>
#define MAX 4005

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;
    queue<pair<int,int>>q;
    q.push({1,1});
    while(!q.empty())
    {
        pair<int,int>nou=q.front();
        int l=nou.first;
        int c=nou.second;
        q.pop();
        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;
                q.push({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 138 ms 13072 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 21 ms 12892 KB Output is correct
5 Correct 11 ms 10844 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 6 ms 6492 KB Output is correct
11 Correct 4 ms 6492 KB Output is correct
12 Correct 32 ms 10832 KB Output is correct
13 Correct 11 ms 10840 KB Output is correct
14 Correct 11 ms 10844 KB Output is correct
15 Correct 69 ms 12892 KB Output is correct
16 Correct 135 ms 13052 KB Output is correct
17 Correct 91 ms 12888 KB Output is correct
18 Correct 20 ms 12888 KB Output is correct

Subtask #2
48.125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 42588 KB Output is correct
2 Correct 394 ms 25684 KB Output is correct
3 Execution timed out 2048 ms 94548 KB Time limit exceeded
4 Correct 1367 ms 38228 KB Output is correct
5 Correct 401 ms 68940 KB Output is correct
6 Execution timed out 2075 ms 94804 KB Time limit exceeded
7 Correct 11 ms 43868 KB Output is correct
8 Correct 11 ms 42536 KB Output is correct
9 Correct 13 ms 4700 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 12 ms 43464 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 396 ms 24404 KB Output is correct
14 Correct 191 ms 20748 KB Output is correct
15 Correct 49 ms 21488 KB Output is correct
16 Correct 349 ms 11356 KB Output is correct
17 Correct 1432 ms 40788 KB Output is correct
18 Correct 163 ms 39856 KB Output is correct
19 Correct 1277 ms 38228 KB Output is correct
20 Execution timed out 2062 ms 35348 KB Time limit exceeded
21 Execution timed out 2061 ms 71260 KB Time limit exceeded
22 Correct 387 ms 68940 KB Output is correct
23 Execution timed out 2061 ms 58188 KB Time limit exceeded
24 Correct 344 ms 70740 KB Output is correct
25 Correct 733 ms 94292 KB Output is correct
26 Correct 648 ms 81876 KB Output is correct
27 Correct 881 ms 94428 KB Output is correct
28 Execution timed out 2074 ms 94804 KB Time limit exceeded
29 Execution timed out 2039 ms 94800 KB Time limit exceeded
30 Execution timed out 2068 ms 94068 KB Time limit exceeded
31 Execution timed out 2045 ms 75084 KB Time limit exceeded
32 Execution timed out 2071 ms 94812 KB Time limit exceeded