oj.uz

Submission #1108090

# Submission time Handle Problem Language Result Execution time Memory
1108090 2024-11-02T17:57:26 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 577 ms 230140 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 4e3 +5, inf = INT_MAX, LL = 30;
 
int depth[sze][sze];
char arr[sze][sze];
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
int n,m;
void rush(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            depth[i][j]=inf;
            cin>>arr[i][j];
        }
    }
    
    deque<pair<int,int>> q;
    q.push_back({0,0});
    depth[0][0]=1;
    int ans=1;

    while(!q.empty()){
        pair<int,int> node = q.front();
        q.pop_front();
        ans=max(ans,depth[node.first][node.second]);
        for(int i=0;i<4;i++){
            int x=node.first + dx[i];
            int y=node.second + dy[i];
            if(min(x,y)>=0 && x<n && y<m && arr[x][y]!='.'){
                if(depth[x][y] >( depth[node.first][node.second] + (arr[node.first][node.second]!=arr[x][y]) )){
                    depth[x][y] = ( depth[node.first][node.second] + (arr[node.first][node.second]!=arr[x][y]) );

                    if(arr[x][y]==arr[node.first][node.second]){
                        q.push_front({x,y});
                    }
                    else{
                        q.push_back({x,y});
                    }
                }
            }
        }
    }

    putr(ans);
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        rush();
    }
 
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21328 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 2 ms 6752 KB Output is correct
4 Correct 6 ms 21584 KB Output is correct
5 Correct 3 ms 12880 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 6736 KB Output is correct
8 Correct 1 ms 6736 KB Output is correct
9 Correct 2 ms 8784 KB Output is correct
10 Correct 3 ms 12880 KB Output is correct
11 Correct 3 ms 10832 KB Output is correct
12 Correct 4 ms 12952 KB Output is correct
13 Correct 3 ms 12880 KB Output is correct
14 Correct 3 ms 12880 KB Output is correct
15 Correct 10 ms 21144 KB Output is correct
16 Correct 10 ms 21328 KB Output is correct
17 Correct 8 ms 19140 KB Output is correct
18 Correct 7 ms 21584 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 136028 KB Output is correct
2 Correct 37 ms 48712 KB Output is correct
3 Correct 216 ms 147472 KB Output is correct
4 Correct 64 ms 70728 KB Output is correct
5 Correct 166 ms 117320 KB Output is correct
6 Correct 577 ms 181932 KB Output is correct
7 Correct 15 ms 140368 KB Output is correct
8 Correct 14 ms 136016 KB Output is correct
9 Correct 2 ms 2384 KB Output is correct
10 Correct 2 ms 2552 KB Output is correct
11 Correct 14 ms 140376 KB Output is correct
12 Correct 2 ms 8784 KB Output is correct
13 Correct 37 ms 48324 KB Output is correct
14 Correct 24 ms 35664 KB Output is correct
15 Correct 19 ms 38480 KB Output is correct
16 Correct 17 ms 17488 KB Output is correct
17 Correct 94 ms 75336 KB Output is correct
18 Correct 78 ms 76104 KB Output is correct
19 Correct 63 ms 73396 KB Output is correct
20 Correct 65 ms 68136 KB Output is correct
21 Correct 140 ms 119372 KB Output is correct
22 Correct 184 ms 116044 KB Output is correct
23 Correct 175 ms 94024 KB Output is correct
24 Correct 133 ms 117320 KB Output is correct
25 Correct 339 ms 141652 KB Output is correct
26 Correct 365 ms 230140 KB Output is correct
27 Correct 418 ms 176692 KB Output is correct
28 Correct 529 ms 167784 KB Output is correct
29 Correct 529 ms 168508 KB Output is correct
30 Correct 464 ms 169156 KB Output is correct
31 Correct 347 ms 118424 KB Output is correct
32 Correct 370 ms 172480 KB Output is correct