Submission #917776

#	Time	Username	Problem	Language	Result	Execution time	Memory
917776		Winter	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	622 ms	211164 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx,avx2,popcnt")
#pragma GCC optimize("O3")
#define int long long
#define pb push_back
#define pii pair<int, int>
const int MA = 1e5+5;
const int MX = 2e9;
const int MD = 998244353;
#define watch(x) cout << #x << "=" << x << endl
void setIO(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
int32_t main(){
  //setIO("nocross"); 
  ios_base::sync_with_stdio(NULL); cin.tie(NULL);
  int n, m; cin >> n >> m;
  vector<vector<char>> v(n+2, vector<char>(m+2, '.'));
  vector<vector<int>> dist(n+2, vector<int>(m+2, MX));
  vector<vector<bool>> vis(n+2, vector<bool>(m+2, false));
  for(int i = 1; i<=n; i++){
    for(int j = 1; j<=m; j++){
      cin >> v[i][j];
    }
  }
  deque<pii> q; q.push_front({1, 1}); 
  dist[1][1]=1; vis[1][1]=true;
  while(!q.empty()){
    int a, b; tie(a, b)=q.front(); q.pop_front();
    if(vis[a+1][b]==false&&v[a+1][b]!='.'){
      int x=0;
      if(v[a][b]!=v[a+1][b]) x=1;
      dist[a+1][b]=min(dist[a+1][b], dist[a][b]+x);
      if(x==0) q.push_front({a+1, b});
      else q.push_back({a+1, b}); 
      vis[a+1][b]=true;
    }
    if(vis[a-1][b]==false&&v[a-1][b]!='.'){
      int x=0;
      if(v[a][b]!=v[a-1][b]) x=1;
      dist[a-1][b]=min(dist[a-1][b], dist[a][b]+x);
      if(x==0) q.push_front({a-1, b});
      else q.push_back({a-1, b}); 
      vis[a-1][b]=true;
    }
    if(vis[a][b+1]==false&&v[a][b+1]!='.'){
      int x=0;
      if(v[a][b]!=v[a][b+1]) x=1;
      dist[a][b+1]=min(dist[a][b+1], dist[a][b]+x);
      if(x==0) q.push_front({a, b+1});
      else q.push_back({a, b+1});
      vis[a][b+1]=true;
    }
    if(vis[a][b-1]==false&&v[a][b-1]!='.'){
      int x=0;
      if(v[a][b]!=v[a][b-1]) x=1;
      dist[a][b-1]=min(dist[a][b-1], dist[a][b]+x);
      if(x==0) q.push_front({a, b-1});
      else q.push_back({a, b-1});
      vis[a][b-1]=true;
    }
  }
  int ans=0;
  for(int i = 1; i<=n; i++){
    for(int j = 1; j<=m; j++){
      if(dist[i][j]!=MX) ans=max(ans, dist[i][j]);
    }
  }
  cout << ans << endl;
  return 0;
}
/*
Amount of animals is the amount of fox and rabbit paths counted separately.
Somehow the answer is related to the amount of components.
int ans=1;
Number of F components completely surrounded by R, or other way around.
The logic is that then there must be one more animal because it is not
possible that F didn't move out and cross over the R.
But there is one counter-case to that logic.
The depth of the most recursive pocket?
Like a circle round' a circle round' a circle and so on..
Distance can be as going from one type of element to another type of element.
Find shortest paths to every place and in that answer array, what
is the biggest distance stored.
Need 0/1 BFS.
Can't count dots for some reason.
*/

Compilation message (stderr)

tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:13:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:14:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   freopen((s + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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