oj.uz

Submission #436692

# Submission time Handle Problem Language Result Execution time Memory
436692 2021-06-24T18:46:31 Z alexis_1729 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 871 ms 153144 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
const int maxn=1e4+1;
const int MOD=1e9+7;
int h,w;
char mx[maxn][maxn]; int ca[maxn][maxn];
#define pi pair<int,int>
int vx[]={1, -1, 0, 0},
    vy[]={0, 0, 1, -1};
    bool good(int x,int y){
       return x>=0 && x<h && y>=0 && y<w && mx[x][y]!='.';

    }
 int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
      cin>>h>>w;
      for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>mx[i][j];
        }
      }
      deque<pi>dq;
      dq.push_back({0,0});int ans=0;
      ca[0][0]=1;
       while(!dq.empty()){
            pi a=dq.front();
               dq.pop_front();
        ans=max(ans,ca[a.first][a.second]);

        for(int i=0;i<4;i++){
                int x,y;
              x=a.first+vx[i];y=a.second+vy[i];
               if(good(x,y) &&  ca[x][y]==0){
                         if(mx[x][y]==mx[a.first][a.second]){
                                ca[x][y]=ca[a.first][a.second];
                                dq.push_front({x,y});
                         }else{
                               ca[x][y]=ca[a.first][a.second]+1;
                               dq.push_back({x,y});
                         }
                     }
                  }
              }
    cout<<ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5708 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 10 ms 5408 KB Output is correct
5 Correct 4 ms 3020 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 4 ms 2508 KB Output is correct
11 Correct 4 ms 2228 KB Output is correct
12 Correct 8 ms 3148 KB Output is correct
13 Correct 5 ms 3020 KB Output is correct
14 Correct 4 ms 3056 KB Output is correct
15 Correct 20 ms 5572 KB Output is correct
16 Correct 16 ms 5708 KB Output is correct
17 Correct 13 ms 5456 KB Output is correct
18 Correct 10 ms 5324 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31404 KB Output is correct
2 Correct 65 ms 16848 KB Output is correct
3 Correct 424 ms 92072 KB Output is correct
4 Correct 124 ms 36548 KB Output is correct
5 Correct 321 ms 62684 KB Output is correct
6 Correct 838 ms 140004 KB Output is correct
7 Correct 19 ms 32844 KB Output is correct
8 Correct 18 ms 31376 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 2 ms 456 KB Output is correct
11 Correct 20 ms 32196 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 65 ms 16836 KB Output is correct
14 Correct 37 ms 11460 KB Output is correct
15 Correct 36 ms 14196 KB Output is correct
16 Correct 28 ms 6280 KB Output is correct
17 Correct 164 ms 33020 KB Output is correct
18 Correct 140 ms 39812 KB Output is correct
19 Correct 121 ms 36504 KB Output is correct
20 Correct 100 ms 29068 KB Output is correct
21 Correct 248 ms 62128 KB Output is correct
22 Correct 284 ms 62676 KB Output is correct
23 Correct 295 ms 51548 KB Output is correct
24 Correct 250 ms 58932 KB Output is correct
25 Correct 747 ms 126320 KB Output is correct
26 Correct 551 ms 150532 KB Output is correct
27 Correct 733 ms 153144 KB Output is correct
28 Correct 854 ms 139852 KB Output is correct
29 Correct 871 ms 138344 KB Output is correct
30 Correct 809 ms 141688 KB Output is correct
31 Correct 676 ms 86644 KB Output is correct
32 Correct 708 ms 138364 KB Output is correct