oj.uz

Submission #998393

# Submission time Handle Problem Language Result Execution time Memory
998393 2024-06-13T20:06:42 Z Mil0S Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 430 ms 140736 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn=4001;
char polja[maxn][maxn];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,m;
int depth[maxn][maxn];


bool check(int x,int y){
if(x<0)return 0;
if(y<0)return 0;
if(x>=n)return 0;
if(y>=m)return 0;
if(polja[x][y]=='.') return 0;
return 1;
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  for(int i=0;i<n;++i){
    for(int j=0;j<m;++j){
        cin>>polja[i][j];
    }
  }
  deque<pair<int,int>> q;
  q.push_back({0,0});
int ans=0;
memset(depth,0,sizeof(depth));
depth[0][0]=1;
  while(!q.empty()) {
        pair<int,int> tren=q.front();
  q.pop_front();
    int x,y;
    x=tren.first;
    y=tren.second;
    ans=max(ans,depth[x][y]);
    for(int i=0;i<4;++i){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(check(nx,ny) && depth[nx][ny]==0){
                depth[nx][ny]=depth[x][y];
                if(polja[x][y]==polja[nx][ny]){
                    q.push_front({nx,ny});
                }
                else{
                         ++depth[nx][ny];
                    q.push_back({nx,ny});

                }
            }
    }
  }
  cout<<ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 66396 KB Output is correct
2 Correct 9 ms 64092 KB Output is correct
3 Correct 8 ms 64092 KB Output is correct
4 Correct 12 ms 66652 KB Output is correct
5 Correct 9 ms 64092 KB Output is correct
6 Correct 7 ms 64152 KB Output is correct
7 Correct 7 ms 64144 KB Output is correct
8 Correct 8 ms 64092 KB Output is correct
9 Correct 8 ms 64092 KB Output is correct
10 Correct 9 ms 64092 KB Output is correct
11 Correct 8 ms 64348 KB Output is correct
12 Correct 11 ms 64376 KB Output is correct
13 Correct 9 ms 64348 KB Output is correct
14 Correct 9 ms 64092 KB Output is correct
15 Correct 14 ms 66576 KB Output is correct
16 Correct 16 ms 66396 KB Output is correct
17 Correct 15 ms 66540 KB Output is correct
18 Correct 12 ms 66652 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 78424 KB Output is correct
2 Correct 39 ms 69860 KB Output is correct
3 Correct 197 ms 94292 KB Output is correct
4 Correct 64 ms 76068 KB Output is correct
5 Correct 151 ms 85324 KB Output is correct
6 Correct 419 ms 107972 KB Output is correct
7 Correct 10 ms 78684 KB Output is correct
8 Correct 9 ms 78552 KB Output is correct
9 Correct 9 ms 64092 KB Output is correct
10 Correct 8 ms 64208 KB Output is correct
11 Correct 10 ms 78424 KB Output is correct
12 Correct 8 ms 64088 KB Output is correct
13 Correct 37 ms 69724 KB Output is correct
14 Correct 25 ms 69188 KB Output is correct
15 Correct 23 ms 69208 KB Output is correct
16 Correct 22 ms 66908 KB Output is correct
17 Correct 84 ms 76384 KB Output is correct
18 Correct 68 ms 76352 KB Output is correct
19 Correct 63 ms 75956 KB Output is correct
20 Correct 54 ms 73532 KB Output is correct
21 Correct 123 ms 85584 KB Output is correct
22 Correct 155 ms 85332 KB Output is correct
23 Correct 158 ms 82012 KB Output is correct
24 Correct 122 ms 85328 KB Output is correct
25 Correct 271 ms 94264 KB Output is correct
26 Correct 233 ms 140736 KB Output is correct
27 Correct 334 ms 120836 KB Output is correct
28 Correct 430 ms 107964 KB Output is correct
29 Correct 423 ms 106288 KB Output is correct
30 Correct 359 ms 111576 KB Output is correct
31 Correct 314 ms 86988 KB Output is correct
32 Correct 304 ms 109576 KB Output is correct