Submission #144928

#	Time	Username	Problem	Language	Result	Execution time	Memory
144928		emilem	Raspad (COI17_raspad)	C++14	9 / 100	6055 ms	91568 KiB

raspad

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int n, m;
vector< vector<char> > a;

class Dsu
{
public:
	Dsu()
		: count(0)
	{}
	void MakeSet(int x, int y)
	{
		// cerr << "Make (" << x << ", " << y << ")\n";
		++count;
		par[make_pair(x, y)] = make_pair(x, y);
	}
	pair<int, int> GetSet(int x, int y)
	{
		pair<int, int> p = make_pair(x, y);
		if (par[p] == p)
			return p;
		return par[p] = GetSet(par[p].first, par[p].second);
	}
	void Union(int x1, int y1, int x2, int y2)
	{
		pair<int, int> p1 = GetSet(x1, y1);
		pair<int, int> p2 = GetSet(x2, y2);
		if (p1 == p2)
			return;
		// cerr << "Union (" << x1 << ", " << y1 << ") and (" << x2 << ", " << y2 << ")\n";
		if (sz[p1] > sz[p2])
			swap(p1, p2);
		sz[p2] += sz[p1];
		par[p1] = p2;
		--count;
	}
	int Size() { return count; }

private:
	int count;
	map<pair<int, int>, pair<int, int>> par;
	map<pair<int, int>, int> sz;
};
int PrefAns(int l, int r)
{
	int res = 0;
	Dsu dsu;
	for (int i = l; i <= r; ++i)
	{
		for (int j = 0; j < m; ++j)
			if (a[i][j] == '1')
			{
				dsu.MakeSet(i, j);
				const int di[] = {-1, 0};
				const int dj[] = {0, -1};
				for (int d = 0; d < 2; ++d)
				{
					int i1 = i + di[d], j1 = j + dj[d];
					if (i1 >= l && i1 <= i && j1 >= 0 && j1 < m && a[i1][j1] == '1')
						dsu.Union(i, j, i1, j1);
				}
			}
		// cerr << "**************dsu size: " << dsu.Size() << endl;
		res += dsu.Size();
	}
	/*
	char I;
	cin >> I;
	*/
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	a.resize(n, vector<char>(m));
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> a[i][j];
	int ans = 0;
	for (int i = 0; i < n; ++i)
		ans += PrefAns(i, n - 1);
	cout << ans << endl;

	char I;
	cin >> I;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 17
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39