Submission #1227763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227763		vyaduct	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	962 ms	173728 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/* Somehow, we just link connected componants together
 * and find max distance to (1,1)
 * omg 01 bfs
*/

const int mxN = 4000;
int a[mxN][mxN];
bool visited[mxN][mxN];
int d[mxN][mxN];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

bool valid(int x, int y, int n, int m){
  return x >= 0 && x < n && y >= 0 && y < m;
}

void solve(){
  int n,m; cin>>n>>m;
  for (int i=0;i<n;i++){
    for (int j=0;j<m;j++){
      char c; cin>>c;
      visited[i][j] = false;
      if (c == '.') a[i][j] = 0;
      else if (c == 'F') a[i][j] = 1;
      else a[i][j] = 2;
    }
  }

  pair<int,int> s = {0,0};
  deque<pair<int,int>> q;
  d[s.first][s.second] = 1;
  visited[s.first][s.second] = true;
  q.push_front(s);
  int ans = 0;
  while(!q.empty()){
    pair<int,int> cur = q.front(); q.pop_front();
    ans = max(ans, d[cur.first][cur.second]);
    for (int k=0;k<4;k++){
      int r = cur.first + dx[k], c = cur.second + dy[k];
      if (valid(r, c, n, m)){
        if (!visited[r][c] && a[r][c] > 0){
          if (a[r][c] == a[cur.first][cur.second]){
            d[r][c] = d[cur.first][cur.second];
            q.push_front({r,c});
          } else {
            d[r][c] = d[cur.first][cur.second]+1;
            q.push_back({r,c});
          }
          visited[r][c] = true;
        }
      }
    }
  }

  cout << ans << endl;
}

int main(){
  solve();
  return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70