## Submission #490095

# Submission time Handle Problem Language Result Execution time Memory
490095 2021-11-25T14:17:17 Z keertan Tracks in the Snow (BOI13_tracks) C++17
77.5 / 100
548 ms 112084 KB
```/**
* If you live in imaginary world when your imaginary situation encounter in
* real situation you can't enjoiy it because you have to do pending work.
* {This pending work appeared because you wasted that time for your useless
* imagianry thinking .}
*/
#include<bits/stdc++.h>
using namespace std;
//#define int  int64_t
#define all(x) x.begin(),x.end()
#define all1(x) x.rbegin(),x.rend()
#define sz(x) (int)(x.size())
const int N=4e5+5,mod=1e9+7;

void solve(){
int n,m;
cin>>n>>m;
vector<string> z(n);
for (string &it:z){cin>>it;}
int ans=1;
deque<pair<int,int>> q;
vector<vector<int>> dis(n,vector<int>(n));
dis[0][0]=1;
q.push_back({0,0});
vector<int> dx{1,-1,0,0},dy{0,0,1,-1};
while(!q.empty()){
pair<int,int> u=q.front();
q.pop_front();
ans=max(ans,dis[u.first][u.second]);
for (int i=0;i<4;i++){
int x=u.first+dx[i],y=u.second+dy[i];
if (min(x,y)>=0 && x<n && y<m && z[x][y]!='.' && dis[x][y]==0){
if (z[u.first][u.second]==z[x][y]){
q.push_front({x,y});
dis[x][y]=dis[u.first][u.second];
}
else{
q.push_back({x,y});
dis[x][y]=dis[u.first][u.second]+1;
}
}
}
}
cout<<ans;
}
int32_t main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int tq=1;
//cin>>tq;
for (;tq;tq--){solve();}
}
//is a bruteforce possible?
//think greedier, make more assumptions
// if we you find solution using loop to decrease complexity use bs
//stuck for more than 5 minutes? move on  ```

#### Subtask #1 25.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1612 KB Output isn't correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 1612 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 4 ms 716 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 2 ms 656 KB Output is correct
15 Correct 9 ms 1748 KB Output is correct
16 Incorrect 9 ms 1612 KB Output isn't correct
17 Correct 6 ms 1612 KB Output is correct
18 Correct 5 ms 1612 KB Output is correct

#### Subtask #2 52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 57684 KB Output is correct
2 Correct 34 ms 8268 KB Output is correct
3 Correct 165 ms 81036 KB Output is correct
4 Incorrect 51 ms 18380 KB Output isn't correct
5 Correct 126 ms 45612 KB Output is correct
6 Correct 548 ms 94676 KB Output is correct
7 Correct 30 ms 63168 KB Output is correct
8 Correct 28 ms 57672 KB Output is correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Incorrect 1 ms 332 KB Output isn't correct
11 Correct 31 ms 60740 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 33 ms 8256 KB Output is correct
14 Incorrect 17 ms 4684 KB Output isn't correct
15 Correct 13 ms 5452 KB Output is correct
16 Incorrect 2 ms 1740 KB Output isn't correct
17 Correct 87 ms 20804 KB Output is correct
18 Correct 55 ms 20448 KB Output is correct
19 Incorrect 50 ms 18380 KB Output isn't correct
20 Incorrect 12 ms 16204 KB Output isn't correct
21 Correct 116 ms 48344 KB Output is correct
22 Correct 125 ms 45556 KB Output is correct
23 Incorrect 130 ms 33608 KB Output isn't correct
24 Correct 107 ms 48436 KB Output is correct
25 Correct 358 ms 80932 KB Output is correct
26 Correct 335 ms 112084 KB Output is correct
27 Correct 407 ms 107548 KB Output is correct
28 Correct 538 ms 94752 KB Output is correct
29 Correct 521 ms 93100 KB Output is correct
30 Correct 456 ms 95812 KB Output is correct
31 Correct 468 ms 52264 KB Output is correct
32 Correct 343 ms 96328 KB Output is correct