Submission #653104

#	Time	Username	Problem	Language	Result	Execution time	Memory
653104		pauloamed	Tracks in the Snow (BOI13_tracks)	C++14	31.77 / 100	2103 ms	1048580 KiB

tracks

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

const int MAXN = 4010;

int n, m; 
string M[MAXN];
int id[MAXN][MAXN];
int curr_id;

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

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

vector<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){
    cin >> M[i];
  }

  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(id[i][j] == 0 && ok(i, j)){
        queue<pair<int,int>> q;
        q.push({i, j});
        id[i][j] = ++curr_id;
        while(q.size()){
          auto [x, y] = q.front();
          q.pop();

          for(int k = 0; k < 4; ++k){
            int ni = x + DI[k];
            int nj = y + DJ[k];
            if(ok(ni, nj) && id[ni][nj] == 0 && M[ni][nj] == M[i][j]){
              id[ni][nj] = id[x][y];
              q.push({ni, nj});
            }
          }
        }
      }
    }
  }

  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(ok(i, j)){
        for(int k = 0; k < 4; ++k){
          int ni = i + DI[k];
          int nj = j + DJ[k];
          if(ok(ni, nj) && M[ni][nj] != M[i][j]){
            v[id[i][j]].push_back(id[ni][nj]);
          }
        }
      }
    }
  }

  for(int i = 0; i < curr_id; ++i){
    sort(v[i].begin(), v[i].end());
    v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
  }

  cout << solve(1, -1) << "\n";

}

Compilation message (stderr)

tracks.cpp: In function 'int32_t main()':
tracks.cpp:43:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |           auto [x, y] = q.front();
      |                ^

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