## Submission #490089

# Submission time Handle Problem Language Result Execution time Memory
490089 2021-11-25T14:08:42 Z keertan Tracks in the Snow (BOI13_tracks) C++17
77.5 / 100
536 ms 123920 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=0;
deque<pair<int,int>> q;
vector<vector<int>> dis(n,vector<int>(n));
dis[0][0]=1;
q.emplace_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.emplace_front(x,y);
dis[x][y]=dis[u.first][u.second];
}
else{
q.emplace_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 10 ms 1740 KB Output isn't correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 6 ms 1740 KB Output is correct
5 Correct 2 ms 836 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 308 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 708 KB Output is correct
11 Correct 2 ms 580 KB Output is correct
12 Correct 5 ms 844 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 2 ms 716 KB Output is correct
15 Correct 7 ms 1864 KB Output is correct
16 Incorrect 9 ms 1740 KB Output isn't correct
17 Correct 6 ms 1712 KB Output is correct
18 Correct 5 ms 1740 KB Output is correct

#### Subtask #2 52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 57804 KB Output is correct
2 Correct 32 ms 9692 KB Output is correct
3 Correct 186 ms 96520 KB Output is correct
4 Incorrect 56 ms 21932 KB Output isn't correct
5 Correct 104 ms 54212 KB Output is correct
6 Correct 536 ms 110240 KB Output is correct
7 Correct 29 ms 63164 KB Output is correct
8 Correct 35 ms 57644 KB Output is correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Incorrect 0 ms 332 KB Output isn't correct
11 Correct 25 ms 60900 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 33 ms 9564 KB Output is correct
14 Incorrect 20 ms 5452 KB Output isn't correct
15 Correct 13 ms 6316 KB Output is correct
16 Incorrect 2 ms 2252 KB Output isn't correct
17 Correct 81 ms 24568 KB Output is correct
18 Correct 50 ms 24164 KB Output is correct
19 Incorrect 46 ms 21896 KB Output isn't correct
20 Incorrect 12 ms 19404 KB Output isn't correct
21 Correct 104 ms 57208 KB Output is correct
22 Correct 100 ms 54260 KB Output is correct
23 Incorrect 142 ms 41076 KB Output isn't correct
24 Correct 101 ms 57156 KB Output is correct
25 Correct 268 ms 96496 KB Output is correct
26 Correct 291 ms 123920 KB Output is correct
27 Correct 420 ms 123044 KB Output is correct
28 Correct 495 ms 110224 KB Output is correct
29 Correct 521 ms 108512 KB Output is correct
30 Correct 451 ms 111076 KB Output is correct
31 Correct 421 ms 62132 KB Output is correct
32 Correct 332 ms 111844 KB Output is correct