Submission #1319615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319615		tkm_algorithms	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1503 ms	388616 KiB

tracks

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 1e9+7;
const int N = 4001;
int a[N*N], vis[N*N];
vector<int> g[N*N];

int find(int x) {
	if (a[x] == x)return x;
	return a[x] = find(a[x]);
}

void unite(int x, int y) {
	x = find(x), y = find(y);
	a[x] = y;
}

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

int c[N][N];
int n, m;

bool can(int i, int j) {
	if (i < 0 || i >= n || j < 1 || j > m)return false;
	return true;
}

int res = 0;

void solve() {
	cin >> n >> m;
	vector<string> s(n);
	rep(i, 0, n*m+1)a[i] = i;
	rep(i, 0, n) {
		cin >> s[i];
		s[i] = '&'+s[i];
	}
	
	rep(i, 0, n)
		rep(j, 1, m+1)
			rep(k, 0, 4) {
				int x = i+dx[k], y = j+dy[k];
				if (can(x, y) && s[x][y] != '.' && s[x][y] == s[i][j])unite(i*m+j, x*m+y);
			}
	
	
	int cnt = 0;
	vector<int> nd(n*m+10);
	rep(i, 0, n)
		rep(j, 1, m+1) {
			if (s[i][j] == '.')continue;
			int x = find(i*m+j);
			if (vis[x])continue;
			nd[x] = ++cnt, vis[x] = 1;
		}
	
	rep(i, 0, n)
		rep(j, 1, m+1)
			rep(k, 0, 4) {
				int x = i+dx[k], y = j+dy[k];
				if (can(x, y) && s[x][y] != '.' && s[x][y] != s[i][j] && s[i][j] != '.') {
					x = find((i+dx[k])*m+j+dy[k]), y = find(i*m+j);
					g[nd[x]].push_back(nd[y]);
				}
			}
	
	memset(vis, 0, sizeof vis);
	
	queue<P> q;
	q.push(P(1, 1));
	vis[1] = 1;
	
	while (!q.empty()) {
		auto &[x, y] = q.front(); q.pop();
		res = max(res, y);
		for (auto i: g[x])
			if (!vis[i]) {
				vis[i] = 1;
				q.push({i, y+1});
			}
	}
	cout << res << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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