oj.uz

Submission #844882

# Submission time Handle Problem Language Result Execution time Memory
844882 2023-09-06T06:50:15 Z elotelo966 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 470 ms 236872 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY 1e11
#define mod 100000000
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mid (start+end)/2
char dizi[4005][4005];
int cev=0,x[4]={1,-1,0,0},y[4]={0,0,1,-1},dep[4005][4005],n,m;

inline int bfs(){
    deque <pair<int,int>> de;
    de.push_back({0,0});
    dep[0][0]=1;
    while(de.size()){
        int x1=de.front().first;
        int y1=de.front().second;

        de.pop_front();
        cev=max(cev,dep[x1][y1]);
        for(int i=0;i<4;i++){
            int yx=x1+x[i],yy=y1+y[i];
            if(yx<0 || yx>=n || yy<0 || yy>=m)continue;
            if(dizi[yx][yy]=='.')continue;
            if(dep[yx][yy]!=0)continue;
            if(dizi[yx][yy]==dizi[x1][y1]){
                dep[yx][yy]=dep[x1][y1];
                de.push_front({yx,yy});
            }else{
                dep[yx][yy]=dep[x1][y1]+1;
                de.push_back({yx,yy});
            }
        }
    }
    return cev;
}

int32_t main(){
    faster
    cin>>n>>m;
    string deg;
    for(int i=0;i<n;i++){
        cin>>deg;
        for(int j=0;j<m;j++){
            dizi[i][j]=deg[j];
        }
    }
    cout<<bfs()<<'\n';
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8536 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 6 ms 8284 KB Output is correct
5 Correct 2 ms 4184 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2820 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 2 ms 3676 KB Output is correct
11 Correct 2 ms 3676 KB Output is correct
12 Correct 4 ms 4324 KB Output is correct
13 Correct 2 ms 4188 KB Output is correct
14 Correct 2 ms 4188 KB Output is correct
15 Correct 8 ms 8284 KB Output is correct
16 Correct 9 ms 8644 KB Output is correct
17 Correct 7 ms 8284 KB Output is correct
18 Correct 5 ms 8300 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31232 KB Output is correct
2 Correct 27 ms 19516 KB Output is correct
3 Correct 136 ms 91516 KB Output is correct
4 Correct 45 ms 47360 KB Output is correct
5 Correct 109 ms 71764 KB Output is correct
6 Correct 456 ms 184260 KB Output is correct
7 Correct 12 ms 32600 KB Output is correct
8 Correct 9 ms 31324 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2808 KB Output is correct
11 Correct 9 ms 32092 KB Output is correct
12 Correct 1 ms 3164 KB Output is correct
13 Correct 27 ms 19640 KB Output is correct
14 Correct 16 ms 12868 KB Output is correct
15 Correct 16 ms 19292 KB Output is correct
16 Correct 15 ms 7664 KB Output is correct
17 Correct 65 ms 36692 KB Output is correct
18 Correct 53 ms 51824 KB Output is correct
19 Correct 46 ms 47440 KB Output is correct
20 Correct 36 ms 31696 KB Output is correct
21 Correct 85 ms 65364 KB Output is correct
22 Correct 111 ms 72020 KB Output is correct
23 Correct 124 ms 58044 KB Output is correct
24 Correct 83 ms 63856 KB Output is correct
25 Correct 364 ms 157268 KB Output is correct
26 Correct 279 ms 236872 KB Output is correct
27 Correct 352 ms 210504 KB Output is correct
28 Correct 470 ms 184180 KB Output is correct
29 Correct 450 ms 181324 KB Output is correct
30 Correct 400 ms 189912 KB Output is correct
31 Correct 330 ms 118696 KB Output is correct
32 Correct 299 ms 181708 KB Output is correct