oj.uz

Submission #1120613

# Submission time Handle Problem Language Result Execution time Memory
1120613 2024-11-28T08:22:17 Z yazansh Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 657 ms 212696 KB 
/*
this code written by :
shimutski_zoro
*/
#include <bits/stdc++.h> 
 
using namespace std; 
 
#define yon(x) cout<<((x)?"YES\n":"NO\n"); 
#define all(x) x.begin(),x.end() 
#define rall(x) x.rbegin(),x.rend() 
#define ff first 
#define ss second 
#define em emplace 
#define emp emplace_back 
#define rep(i,j,k) for(int i=j;i<=k;i++) 
#define per(i,j,k) for(int i=k;i>=j;i--) 
#define forp(x,y,a) for(auto &[x,y]:(a)) 
typedef long long  ll; 
typedef pair<ll,ll> pll; 
typedef vector<ll> vl; 
typedef vector<pll> vpl; 
typedef vector<vl> vvl; 
typedef vector<vpl> vvpl; 
typedef vector<string> vs; 
typedef vector<set<ll> >vst;
typedef deque<ll> dl; 
const int mod=1e9+7;
const ll inf =1e18+1; 
const int N=1e6+1; 
const ll dx[]={1,0,-1,0},dy[]={0,1,0,-1}; 
void solve(){ 
    ll n,m;
    cin>>n>>m;
    vs g(n);
    rep(i,0,n-1){
        cin>>g[i];
    }             
    vvl d(n,vl(m));
    d[0][0]=1;
    deque<pll>dq;
    dq.emp(0,0);
    auto is=[&](ll x,ll y){
    return x>=0&&x<n&&y>=0&&y<m&&g[x][y]!='.';
    };
    ll ans=0;
    while(!dq.empty()){
ll x=dq.front().ff,y=dq.front().ss;
ans=max(ans,d[x][y]);
dq.pop_front();
rep(i,0,3){
    ll nx=x+dx[i],ny=y+dy[i];
    if(is(nx,ny)&&!d[nx][ny]){
        d[nx][ny]=d[x][y];
if(g[x][y]==g[nx][ny]){
    dq.push_front({nx,ny});

}else{
    d[nx][ny]++;
    dq.push_back({nx,ny});
}
    }
}
    }
    cout<<ans;                                                
}

signed main() { 

    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    #ifdef Usaco 
    string f="guard"; 
    freopen((f+".in").c_str(),"r",stdin); 
    freopen((f+".out").c_str(),"w",stdout); 
    #endif 
    int t = 1; 
    //cin >> t; 
    while (t--) { 
        solve();  
    } 
} 
/* 
example:

*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2896 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 6 ms 2128 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 2 ms 848 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 2 ms 1104 KB Output is correct
14 Correct 2 ms 1104 KB Output is correct
15 Correct 8 ms 2760 KB Output is correct
16 Correct 9 ms 2640 KB Output is correct
17 Correct 8 ms 2384 KB Output is correct
18 Correct 4 ms 2128 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1148 KB Output is correct
2 Correct 37 ms 14416 KB Output is correct
3 Correct 197 ms 143620 KB Output is correct
4 Correct 64 ms 33868 KB Output is correct
5 Correct 115 ms 80712 KB Output is correct
6 Correct 595 ms 171632 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 2 ms 1028 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 2 ms 1020 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 34 ms 14824 KB Output is correct
14 Correct 21 ms 8552 KB Output is correct
15 Correct 13 ms 9296 KB Output is correct
16 Correct 15 ms 5968 KB Output is correct
17 Correct 113 ms 37644 KB Output is correct
18 Correct 50 ms 35920 KB Output is correct
19 Correct 68 ms 34128 KB Output is correct
20 Correct 47 ms 32324 KB Output is correct
21 Correct 113 ms 84168 KB Output is correct
22 Correct 116 ms 83424 KB Output is correct
23 Correct 160 ms 69448 KB Output is correct
24 Correct 107 ms 81480 KB Output is correct
25 Correct 220 ms 145608 KB Output is correct
26 Correct 309 ms 210176 KB Output is correct
27 Correct 420 ms 212696 KB Output is correct
28 Correct 622 ms 171428 KB Output is correct
29 Correct 657 ms 167808 KB Output is correct
30 Correct 567 ms 178836 KB Output is correct
31 Correct 479 ms 92832 KB Output is correct
32 Correct 444 ms 192252 KB Output is correct