oj.uz

Submission #553769

# Submission time Handle Problem Language Result Execution time Memory
553769 2022-04-26T22:08:40 Z Uzouf Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1433 ms 348148 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
//#define endl "\n"
const int mod = (int) 1e9 + 7;
const int N=4005;

int n,m,ans,nm;
char c,tmp;
char v[N][N];
int cst[N][N];
bool vis[N][N];
bool bl;

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

bool chk(int i,int j) {
  return i>=0 && j>=0 && i<n && j<m && !vis[i][j] && v[i][j]!='.';
}

void bfs() {
  deque<pair<int,int> > q; q.push_front({0,0});
  while (!q.empty()) {
    int i=q.front().first;
    int j=q.front().second;
    q.pop_front();
    vis[i][j]=true;
    ans=max(ans,cst[i][j]);

    for (int p=0;p<4;p++) {
      int ii=i+dx[p],jj=j+dy[p];

      if (chk(ii,jj)) {
      if (v[i][j]==v[ii][jj]) {cst[ii][jj]=cst[i][j]; q.push_front({ii,jj});}
      else {cst[ii][jj]=cst[i][j]+1;q.push_back({ii,jj});}
      }

    }
  }

}


signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(".in", "r", stdin); freopen(".out", "w", stdout);

    cin>>n>>m;
    for (int i=0;i<n;i++) {
      for (int j=0;j<m;j++) {
        cin>>v[i][j];
      }
    }

    cst[0][0]=1; bfs();
    cout<<ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8524 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 16 ms 8360 KB Output is correct
5 Correct 5 ms 4392 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 4 ms 3540 KB Output is correct
11 Correct 5 ms 3284 KB Output is correct
12 Correct 11 ms 4692 KB Output is correct
13 Correct 5 ms 4312 KB Output is correct
14 Correct 5 ms 4368 KB Output is correct
15 Correct 23 ms 8032 KB Output is correct
16 Correct 28 ms 8524 KB Output is correct
17 Correct 16 ms 8000 KB Output is correct
18 Correct 16 ms 8332 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 45932 KB Output is correct
2 Correct 82 ms 22520 KB Output is correct
3 Correct 441 ms 92876 KB Output is correct
4 Correct 116 ms 52084 KB Output is correct
5 Correct 240 ms 75836 KB Output is correct
6 Correct 1428 ms 225340 KB Output is correct
7 Correct 21 ms 48072 KB Output is correct
8 Correct 21 ms 45940 KB Output is correct
9 Correct 4 ms 980 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 21 ms 47192 KB Output is correct
12 Correct 2 ms 2260 KB Output is correct
13 Correct 83 ms 22308 KB Output is correct
14 Correct 47 ms 15560 KB Output is correct
15 Correct 35 ms 20308 KB Output is correct
16 Correct 41 ms 8576 KB Output is correct
17 Correct 199 ms 42028 KB Output is correct
18 Correct 133 ms 56624 KB Output is correct
19 Correct 118 ms 51732 KB Output is correct
20 Correct 108 ms 35276 KB Output is correct
21 Correct 258 ms 66864 KB Output is correct
22 Correct 241 ms 74948 KB Output is correct
23 Correct 376 ms 60744 KB Output is correct
24 Correct 224 ms 65976 KB Output is correct
25 Correct 611 ms 158124 KB Output is correct
26 Correct 964 ms 348148 KB Output is correct
27 Correct 1241 ms 257344 KB Output is correct
28 Correct 1433 ms 224776 KB Output is correct
29 Correct 1396 ms 221536 KB Output is correct
30 Correct 1306 ms 245444 KB Output is correct
31 Correct 1132 ms 121080 KB Output is correct
32 Correct 1061 ms 223704 KB Output is correct