Submission #1181616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181616		trvhung	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	531 ms	1114112 KiB

tracks

#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

// #define   ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define            ll long long
#define           ull unsigned long long
#define            ld long double
#define            pb push_back
#define  bit(mask, i) ((mask >> i) & 1)
#define            el '\n'
#define             F first
#define             S second

template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};

const int maxn = 4e3 + 5;
int n, m, cur, id[maxn][maxn], dist[maxn * maxn];
char c[maxn][maxn];
vector<int> adj[maxn * maxn];
map<int, bool> mp[maxn * maxn];

void dfs(int x, int y) {
	id[x][y] = cur;
	for (int i = 0; i < 4; ++i) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
		if (id[nx][ny] || c[nx][ny] != c[x][y]) continue;
		dfs(nx, ny);
	}
}

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			cin >> c[i][j];	

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (!id[i][j]) {
				cur++;
				dfs(i, j);
			}

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			for (int k = 0; k < 4; ++k) {
				int nx = i + dx[k], ny = j + dy[k];
				if (nx < 1 || nx > n || ny < 1 || ny > m) continue;

				int u = id[i][j], v = id[nx][ny];
				if (u == v || mp[u].find(v) != mp[u].end()) continue;

				mp[u][v] = mp[v][u] = true;
				adj[u].push_back(v);
				adj[v].push_back(u);
			}

	memset(dist, 0x3f, sizeof(dist));
	queue<int> q; q.push(id[1][1]); dist[id[1][1]] = 0;

	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v: adj[u])
			if (dist[v] > n * m) {
				dist[v] = dist[u] + 1;
				q.push(v);
			}
	}

	cout << *max_element(dist + 1, dist + 1 + cur) + 1;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (!MULTI) solve();
    else {
        int test; cin >> test;
        while (test--) solve();
    }
    
    return 0;
}

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