oj.uz

Submission #860823

# Submission time Handle Problem Language Result Execution time Memory
860823 2023-10-14T12:18:06 Z shahi_45 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1403 ms 450892 KB 
//JAI BAJRANG BALI

#include <bits/stdc++.h>
#include <algorithm>
#include <numeric>
using namespace std;
// #ifndef ONLINE_JUDGE
// #include "./debugging.hpp" // pathname
// #else
// #define debug(...)
// #endif

#define ndl "\n"
typedef long long int ll;
typedef unsigned long long int ull;
//#define int long long
// ... Rest of your template code ...

#define out1(x) cout<<x<<"\n";
#define out(x) cout<<x<<" ";
#define vi  vector<int>
#define vll  vector<ll>
#define vs vector<string>
#define sortA(a) sort(a.begin(),a.end())
#define sortD(a) sort(a.begin(),a.end(), greater<ll>())
#define yes() std::cout << "YES\n";
#define no() std::cout << "NO\n";
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define p 998244353
using ll = long long;
vll dx={1,-1,0,0};
vll dy={0,0,-1,1};
// 1,0 -1,0 0,-1 0,1
void solve(ll tc){
   ll n,m; cin>>n>>m; vector<string> steps(n); 
   vector<vll> d(n,vll(m,0));
   for(ll i=0;i<n;i++){
    cin>>steps[i];
   } 
   d[0][0]=1;
   ll ans=1;
   deque<vll> q;
   q.push_front({0,0});
   while(q.size()){
    vll v1=q.front(); q.pop_front();
    ll x1=v1[0]; ll y1=v1[1];
    ans=max(ans,d[x1][y1]);
    for(ll i=0;i<4;i++){
        ll new_x=x1+dx[i];
        ll new_y=y1+dy[i];
        if(new_x>=0 and new_y>=0 and new_x<n and new_y<m and (steps[new_x][new_y]!='.')){
            ll weight=0;
            if(steps[new_x][new_y]!=steps[x1][y1]) {
                weight++;
            }
            if(d[new_x][new_y]==0){
                d[new_x][new_y]=d[x1][y1]+weight;
                if(weight==0){
                    q.push_front({new_x,new_y});
                }
                else{
                    q.push_back({new_x,new_y});
                }
            }
        }
    }
   }
   out1(ans);
   

}


signed main(){
    ll T=1;
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
   //cin>>T;
    for (ll tc = 1; tc <=T; tc++) solve(tc);
    return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2904 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 11 ms 2908 KB Output is correct
5 Correct 2 ms 1116 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 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 5 ms 1116 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct
13 Correct 2 ms 1112 KB Output is correct
14 Correct 2 ms 1116 KB Output is correct
15 Correct 17 ms 2868 KB Output is correct
16 Correct 20 ms 2908 KB Output is correct
17 Correct 10 ms 2652 KB Output is correct
18 Correct 11 ms 2908 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 54 ms 14428 KB Output is correct
3 Correct 293 ms 143444 KB Output is correct
4 Correct 75 ms 34352 KB Output is correct
5 Correct 210 ms 80720 KB Output is correct
6 Correct 1358 ms 235308 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 55 ms 14504 KB Output is correct
14 Correct 31 ms 8536 KB Output is correct
15 Correct 19 ms 9304 KB Output is correct
16 Correct 28 ms 6236 KB Output is correct
17 Correct 144 ms 36948 KB Output is correct
18 Correct 89 ms 35932 KB Output is correct
19 Correct 70 ms 33880 KB Output is correct
20 Correct 68 ms 31064 KB Output is correct
21 Correct 171 ms 83572 KB Output is correct
22 Correct 211 ms 80724 KB Output is correct
23 Correct 275 ms 69864 KB Output is correct
24 Correct 176 ms 81596 KB Output is correct
25 Correct 582 ms 143444 KB Output is correct
26 Correct 949 ms 450892 KB Output is correct
27 Correct 1141 ms 299364 KB Output is correct
28 Correct 1373 ms 243612 KB Output is correct
29 Correct 1403 ms 231336 KB Output is correct
30 Correct 1267 ms 260784 KB Output is correct
31 Correct 909 ms 100176 KB Output is correct
32 Correct 960 ms 239152 KB Output is correct