Submission #1012940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012940		parentoni	Tracks in the Snow (BOI13_tracks)	C++17	51.15 / 100	336 ms	152076 KiB

tracks

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

#define all(x) (x).begin(), (x).end()
#define print(x) for (auto el: x) cout << el << " "; cout << '\n'

using ll = long long;
using llb = long double;
using vl = vector<ll>;
using pll = pair<ll,ll>;

// functions
void setIO(string s) {freopen((s + ".in").c_str(), "r", stdin);freopen((s + ".out").c_str(), "w", stdout);}
void yes() { cout<<"YES\n"; }
void no() { cout<<"NO\n"; }

// geometry
const double PI = 3.14159265358979323846;
double DEG_to_RAD (double d) {return d*PI/180.0;}
double RAD_to_DEG (double r) {return r*180.0/ PI;}

// values
const ll INF = 1e18;
const ll MOD = 1000000007;
const ll MAX_N = 4000;
ll h, w;

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

vector<vector<bool>> board; // 0 if F, 1 if R;
vector<vector<bool>> visited; 
vector<vl> adj;


deque<pair<pll, ll>> q;


ll bfs() {

  q.push_back({{1,1}, 1});
  visited[1][1] = true;
  ll ans = 1;

  while(!q.empty()) {

    ans = max(ans, q.front().second);
    pll cord = q.front().first; ll sc = q.front().second;
    //cout << cord.first << " " << cord.second << " " << q.front().second<< endl;
    q.pop_front();
    for (int i=0;i<4;i++) {
      if (visited[cord.first + dx[i]][cord.second + dy[i]]) continue;

      if (board[cord.first + dx[i]][cord.second + dy[i]] != board[cord.first][cord.second]) {
        q.push_back({{cord.first+dx[i], cord.second+dy[i]}, sc+1});
      } else {
        q.push_front({{cord.first+dx[i], cord.second+dy[i]}, sc});
      }

      visited[cord.first + dx[i]][cord.second + dy[i]] = true;
    }
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> h >> w; board.resize(h+2); visited.resize(h+2);
  for (auto &el: board) el.resize(w+2);
  for (auto &el: visited) el.resize(w+2);
 
  fill(visited[0].begin(),visited[0].end(), 1);
  for (int i=0;i<=h+1;i++) {visited[i][0] = true; visited[i][w+1] = true;} 
  fill(visited[h+1].begin(), visited[h+1].end(), 1);

  for (int i=1;i<=h;i++) {
    string t; cin >> t;
    for (int j=1;j<=w;j++) {
      board[i][j] = t[j] == 'F'?1:0;
      visited[i][j] = t[j] == '.'?1:0;
    }
  }

  cout << bfs() << "\n";

}

Compilation message (stderr)

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

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