Submission #699757

#	Time	Username	Problem	Language	Result	Execution time	Memory
699757		TAhmed33	Tracks in the Snow (BOI13_tracks)	C++98	2.19 / 100	1499 ms	203848 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int sze[16000001] = {};
int par[16000001] = {};
void init (int x) {
	sze[x] = 1;
	par[x] = x;
}
int f(int x) {
	return (par[x] == x ? x : par[x] = f(par[x]));
}
void merge (int x, int y) {
	x = f(x);
	y = f(y);
	if (x == y) return;
	if (sze[x] > sze[y]) swap(x, y);
	sze[y] += sze[x];
	par[x] = y;
}
int main () {
	int n, m;
	cin >> n >> m;
	char arr[n + 1][m + 1];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 1; i <= n * m; i++) init(i);
	int ign[n * m + 1] = {};
	for (int i = 1; i <= n * m; i++) {
		int y = i%m;
		if (y == 0) y = m;
		int x = (i - y)/m + 1;
		if (arr[x][y] == '.') {
			ign[i] = 1;
			continue;
		}
		if (x < n && arr[x + 1][y] != '.') merge(i, i + m);
		if (x > 1 && arr[x - 1][y] != '.') merge(i, i - m);
		if (y < m && arr[x][y + 1] != '.') merge(i, i + 1);
		if (y > 1 && arr[x][y - 1] != '.') merge(i, i - 1);
	}
	map <int, set <char>> pp;
	for (int i = 1; i <= n * m; i++) {
		if (ign[i]) continue;
		int y = i%m;
		if (!y) y = m;
		pp[f(i)].insert(arr[(i - y)/m + 1][y]);
	}
	int cnt = 0;
	for (auto i : pp) {
		cnt += i.second.size();
	}
	cout << cnt << '\n';
}

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