Submission #1153878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153878		gelastropod	Selotejp (COCI20_selotejp)	C++20	0 / 110	0 ms	324 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> tree;

int fin(int n) {
	if (tree[n] == n) return n;
	return tree[n] = fin(tree[n]);
}

void join(int a, int b) {
	a = fin(a);
	b = fin(b);
	if (a == b) return;
	tree[a] = b;
}

signed main() {
	int n, m;
	string s;
	cin >> n >> m;
	for (int i = 0; i < n * m; i++) tree.push_back(i);
	vector<vector<bool>> closed(n, vector<bool>(m, false));
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < m; j++)
			closed[i][j] = s[j] == '#';
	}
	pair<int, int> dirs[] = {
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1}
	};
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!closed[i][j]) continue;
			vector<int> neighs;
			for (int k = 0; k < 4; k++) {
				int ci = i + dirs[k].first;
				int cj = j + dirs[k].second;
				if (ci == -1 || ci == n || cj == -1 || cj == m) continue;
				if (closed[ci][cj]) {
					join(i * m + j, ci * m + cj);
					neighs.push_back(ci * m + cj);
				}
			}
			if (neighs.size() == 2 && (neighs[0] / m != neighs[1] / m && neighs[0] % m != neighs[1] % m))
				ans++;
		}
	}
	set<int> ss;
	for (int j : tree) {
		int i = fin(j);
		if (closed[i / m][i % m])
			ss.insert(i);
	}
	cout << ss.size() + ans << '\n';
}

• Subtask 1: 0 / 35
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40