Submission #1020404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020404		NguyenPhucThang	Tracks in the Snow (BOI13_tracks)	C++14	19.38 / 100	663 ms	177060 KiB

tracks

#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int base = 31;
const ll mod = 1e9 + 7;
const ll oo = 1e18;
const int N = 4005;

char a[N][N];
int comp[N][N], dis[N * N], cnt = 0;
int dx[] = {0, 1, 0, -1},
   dy[] ={1, 0, -1, 0};

vector<int> g[N];
map<pii, bool> con;

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
  
   int m, n;
   cin >> m >> n;
   forr(i, 1, m) forr(j, 1, n) cin >> a[i][j];

   forr(i, 1, n){
      forr(j, 1, n){
         if (!comp[i][j] && a[i][j] != '.'){
            comp[i][j] = ++cnt;
            queue<pii> q;
            q.push({i, j});
            while (!q.empty()){
               pii u = q.front();
               q.pop();
               forr(k, 0, 3){
                  int nx = u.fi + dx[k], ny = u.se + dy[k];
                  if (1 <= nx && nx <= m && 1 <= ny && ny <= n && a[nx][ny] == a[i][j] && !comp[nx][ny]){
                     q.push({nx, ny});
                     comp[nx][ny] = comp[i][j];
                  } 
               }
            }
         }
      }
   }

   forr(i, 1, n){
      forr(j, 1, n){
         forr(k, 0, 3){
            int nx = i + dx[k], ny = j + dy[k];
            if (1 <= nx && nx <= m && 1 <= ny && ny <= n && comp[i][j] && comp[nx][ny]){
               if (comp[i][j] != comp[nx][ny] && !con[{comp[i][j], comp[nx][ny]}]){
                  int u = comp[i][j], v = comp[nx][ny];
                  g[u].pb(v);
                  g[v].pb(u);
                  con[{u, v}] = con[{v, u}] = true;
               }
            }
         }
      }
   }

   dis[1] = 1;
   queue<int> q;
   q.push(1);
   int res = 0;
   while (!q.empty()){
      int u = q.front();
      q.pop();
      res = max(res, dis[u]);
      for(int v : g[u]){
         if (!dis[v]) {
            dis[v] = dis[u] + 1;
            q.push(v);
         }
      }
   }

   cout << res;



   return 0;
}

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