제출 #1289545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289545		g4yuhg	Tracks in the Snow (BOI13_tracks)	C++20	40.94 / 100	2142 ms	1060520 KiB

tracks

#include<bits/stdc++.h>
typedef long long ll;
#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 4005
#define LOG 16
using namespace std;

bool ghuy4g;

const ll hx[] = {-1, 0, 1, 0};
const ll hy[] = {0, 1, 0, -1};

ll n, m, tong;
char a[N][N];

ll idx[N][N], cur, par[N * N];

bool vst[N * N];

pii p[N * N];

vector<ll> vt[N * N];

ll find(ll u) {
	if (par[u] < 0) return u;
	return par[u] = find(par[u]);
}

void join(ll u, ll v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	if (par[u] <= par[v]) {
		par[u] += par[v];
		par[v] = u;
	}
	else {
		par[v] += par[u];
		par[u] = v;
	}
}

void solve() {
	ll ans = 0;
	vector<ll> nxt;
	nxt.push_back(find(idx[n][m]));
	vector<ll> cur = nxt;
	nxt.clear();
	while (true) {
		if (cur.size() == 0) break;
		ans ++ ;
		for (auto u : cur) {
			for (auto it : vt[u]) {
				vst[it] = 1;
				for (int z = 0; z < 4; z ++) {
					ll dx = p[it].fi + hx[z];
					ll dy = p[it].se + hy[z];
					if (dx < 1 || dy < 1 || dx > n || dy > m) continue;
					if (a[dx][dy] == a[p[it].fi][p[it].se] || a[dx][dy] == '.') continue; // cung ma ke => cung tplt
					ll root = find(idx[dx][dy]);
					if (vst[root] == 0) {
						vst[root] = 1;
						nxt.push_back(root);
					}
				}
			}
		}
		cur = nxt;
		nxt.clear();
	}
	cout << ans << endl;
}

void pre() {
	for (int i = 1; i <= cur; i ++) par[i] = -1;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			if (a[i][j] == '.') continue;
			for (int z = 0; z < 4; z ++) {
				ll dx = i + hx[z], dy = j + hy[z];
				if (dx < 1 || dy < 1 || dx > n || dy > m) continue;
				if (a[dx][dy] != a[i][j]) continue;
				join(idx[dx][dy], idx[i][j]);
			}
		}
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			if (a[i][j] == '.') continue;
			ll root = find(idx[i][j]);
			vt[root].push_back(idx[i][j]);
		}
	}
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
    	for (int j = 1; j <= m; j ++) {
    		cin >> a[i][j];
    		if (a[i][j] != '.') {
    			tong ++ ;
    			idx[i][j] = ++ cur;
    			p[cur] = {i, j};
    		}
    	}
    }
    pre();
    solve();
    
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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