Submission #653109

#	Time	Username	Problem	Language	Result	Execution time	Memory
653109		pauloamed	Tracks in the Snow (BOI13_tracks)	C++14	73.13 / 100	872 ms	1048576 KiB

tracks

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

const int MAXN = 4010;

int n, m; 
bool M[MAXN][MAXN];
bool on[MAXN][MAXN];
int curr_id;

bool ok(int i, int j){
  if(i < 0 || j < 0 || i >= n || j >= m) return false;
  return on[i][j];
}

int DI[] = {0, 0, -1, 1};
int DJ[] = {-1, 1, 0, 0};

set<int> v[MAXN * MAXN];

int solve(int x, int p){
  int ans = 0;
  for(auto y : v[x]) if(y != p){
    ans = max(ans, solve(y, x));
  }
  return ans + 1;
}

int32_t main(){
  cin.tie(NULL)->sync_with_stdio(false);
  cin >> n >> m;
  for(int i = 0; i < n; ++i){
    string s; cin >> s;
    for(int j = 0; j < n; ++j){
      if(s[j] == '.') on[i][j] = false;
      else{
        on[i][j] = true;
        M[i][j] = (s[j] == 'F');
      }
    }
  }

  int ans = 0;
  struct Node{
    int i, j, d;
  };
  deque<Node> q;
  q.push_front({0, 0, 1});
  on[0][0] = false;
  while(q.size()){
    auto [i, j, d] = q.front();
    q.pop_front();

    ans = max(ans, d);

    for(int k = 0; k < 4; ++k){
      int ni = i + DI[k];
      int nj = j + DJ[k];
      if(ok(ni, nj)){
        on[ni][nj] = false;
        if(M[ni][nj] != M[i][j]){
          q.push_back({ni, nj, d + 1});
        }else{
          q.push_front({ni, nj, d});
        }
      }
    }
  }

  cout << ans << "\n";

}

Compilation message (stderr)

tracks.cpp: In function 'int32_t main()':
tracks.cpp:51:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     auto [i, j, d] = q.front();
      |          ^

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