oj.uz

Submission #1097499

# Submission time Handle Problem Language Result Execution time Memory
1097499 2024-10-07T13:36:45 Z jaintanmayp Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 811 ms 250852 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
// #define ll double
#define vl vector<ll>
#define vpll vector<pair<ll,ll>>
#define vvl vector<vector<ll>> 
#define vvc vector<vector<char>> 
#define newl cout << endl;
#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl; 


const ll N = 4*(1e3) + 2;
// vvl adj(N);
vector<string> field(N);

// vector<ll> vis(N,0);
ll n, m;

ll dr[4] = {+1, 0, 0, -1};
ll dc[4] = {0, -1, +1, 0};

bool check(ll r, ll c){
    if(r < 0 || r >= n) return false;
    if(c < 0 || c >= m) return false;
    if(field[r][c] == '.') return false;
    
    return true;
}

void solve(){
 
    cin >> n >> m;
    
    for(ll i = 0; i < n; i++){
        cin >> field[i];
    }
    
    deque<pair<ll,ll>> q;
    vvl dist(n, vl(m, -1));
    q.push_back({0,0});
    dist[0][0] = 1;
    
    ll ans = 1;
    
    while(!q.empty()){
        auto it =  q.front();
        q.pop_front();
        ll r  = it.first;
        ll c =  it.second;

        
        for(ll i = 0; i < 4; i++){
            ll nr = r + dr[i];
            ll nc = c + dc[i];
            
            ans = max(ans , dist[r][c]);
            if(!check(nr, nc)) continue;
            
            if(dist[nr][nc] == -1){
                if(field[r][c] == field[nr][nc]){
                    dist[nr][nc] = dist[r][c];
                    q.push_front({nr, nc});
                }
                else{
                    dist[nr][nc] = dist[r][c] + 1;
                    q.push_back({nr, nc});
                    // ans++;
                }
            }
            
        }
        
    }
    

    cout << ans << endl;
    
    
    return;
 
}
 
int main(){
    
    ll t=1;
    // cin>>t;
    while(t>0){
        solve();
        t--;
    }
    
    
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3164 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 2552 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 680 KB Output is correct
10 Correct 2 ms 1164 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 5 ms 1372 KB Output is correct
13 Correct 3 ms 1372 KB Output is correct
14 Correct 3 ms 1372 KB Output is correct
15 Correct 11 ms 3288 KB Output is correct
16 Correct 14 ms 3164 KB Output is correct
17 Correct 9 ms 3092 KB Output is correct
18 Correct 6 ms 2396 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 54 ms 16640 KB Output is correct
3 Correct 470 ms 171608 KB Output is correct
4 Correct 101 ms 40532 KB Output is correct
5 Correct 240 ms 91132 KB Output is correct
6 Correct 803 ms 200232 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 2 ms 1116 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 52 ms 16688 KB Output is correct
14 Correct 29 ms 10076 KB Output is correct
15 Correct 26 ms 11100 KB Output is correct
16 Correct 23 ms 7004 KB Output is correct
17 Correct 141 ms 43860 KB Output is correct
18 Correct 109 ms 43348 KB Output is correct
19 Correct 108 ms 40528 KB Output is correct
20 Correct 80 ms 37384 KB Output is correct
21 Correct 209 ms 94240 KB Output is correct
22 Correct 238 ms 91220 KB Output is correct
23 Correct 272 ms 78268 KB Output is correct
24 Correct 227 ms 92496 KB Output is correct
25 Correct 458 ms 171604 KB Output is correct
26 Correct 420 ms 221880 KB Output is correct
27 Correct 642 ms 250852 KB Output is correct
28 Correct 811 ms 200576 KB Output is correct
29 Correct 784 ms 196048 KB Output is correct
30 Correct 737 ms 208540 KB Output is correct
31 Correct 520 ms 103644 KB Output is correct
32 Correct 606 ms 216260 KB Output is correct