Submission #715531

#	Time	Username	Problem	Language	Result	Execution time	Memory
715531		Behradm	Tracks in the Snow (BOI13_tracks)	C++11	93.44 / 100	2103 ms	1027804 KiB

tracks

/**
 *  In the name of GOD
 *  author : Behradm
**/
#include "bits/stdc++.h"
 
using namespace std;
 
#define sz(x) (int) ((x).size())
 
const int N = 4e3 + 5;
char s[N][N];
int tag[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
 
int n, m;
 
bool Good(int x, int y) {
  return (0 <= x && x < n && 0 <= y && y < m && s[x][y] != '.');
}
 
void dfs(int i, int j, int c) {
  tag[i][j] = c;
  for (int k = 0; k < 4; k++) {
    int x = i + dx[k], y = j + dy[k];
    if (Good(x, y) && s[x][y] == s[i][j] && tag[x][y] == -1) {
      dfs(x, y, c);
    }
  }
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> s[i][j];
      tag[i][j] = -1;
    }
  }
  
  int c = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (tag[i][j] == -1 && s[i][j] != '.')
        dfs(i, j, c++);
    }
  }
 
  //[0, c - 1]
  vector<vector<int>> g(c);
  set<pair<int, int>> st;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (s[i][j] != 'R')
        continue;
      for (int k = 0; k < 4; k++) {
        int x = i + dx[k], y = j + dy[k];
        if (Good(x, y) && (s[i][j] == 'R' && s[x][y] == 'F')) {
          int p = tag[i][j], q = tag[x][y];
          if (p > q) swap(p, q);
          if (st.find({p, q}) != st.end())
            continue;
          g[p].push_back(q);
          g[q].push_back(p);
          st.insert({p, q});
        }
      }
    }
  }
  
  for (int i = 0; i < c; i++) {
    sort(g[i].begin(), g[i].end());
    g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin());
  }
 
  vector<int> h(c);
  queue<int> q;
  q.push(0), h[0] = 1;
  int ans = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : g[u]) {
      if (h[v] == 0) {
        h[v] = h[u] + 1;
        ans = max(ans, h[v]);
        q.push(v);
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

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