Submission #145041

#	Time	Username	Problem	Language	Result	Execution time	Memory
145041		emilem	Raspad (COI17_raspad)	C++14	0 / 100	6086 ms	4608 KiB

raspad

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
using namespace std;
struct PlatUnion
{
	PlatUnion(int after_, int i1_, int j1_, int i2_, int j2_)
		: after(after_)
		, i1(i1_)
		, j1(j1_)
		, i2(i2_)
		, j2(j2_)
	{}
	int after, i1, j1, i2, j2;
};
bool operator<(const PlatUnion& lhs, const PlatUnion& rhs) { return lhs.after < rhs.after; }

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

struct Dsu
{
public:
	Dsu()
		: count(0)
		, hard(false)
	{}
	void SetHard(Dsu& rhs)
	{
		for (auto it = par.begin(); it != par.end(); ++it)
			plats.insert(it->first);
		swap(*this, rhs);
		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 Count() { return count; }

	bool hard;
	set< pair<int, int> > plats;
	int count;
	map<pair<int, int>, pair<int, int>> par;
	map<pair<int, int>, int> sz;
};

void TryPlatUnion(vector< pair<int, int> >& plats, Dsu dsu, vector<PlatUnion>& platUnions,
	int i1, int j1, int i2, int j2, int after)
{
	int plat1 = -1, plat2 = -1;
	for (int i = 0; i < plats.size(); ++i)
		if (dsu.GetSet(plats[i].first, plats[i].second) == dsu.GetSet(i1, j1))
			plat1 = i;
		else if (dsu.GetSet(plats[i].first, plats[i].second) == dsu.GetSet(i2, j2))
			plat2 = i;
	if (plat1 == -1 || plat2 == -1)
		return;
	platUnions.push_back(PlatUnion(after, plats[plat1].first, plats[plat1].second,
		plats[plat2].first, plats[plat2].second));
}
int PrefAns(int l, int r, int platform = -1, Dsu dsu_ = Dsu())
{
	int res = 0;
	Dsu dsu;
	vector< pair<int, int> > plats;
	bool hard = false;
	if (platform != -1)
		for (int j = 0; j < m; ++j)
		{
			if (a[platform][j] == 1)
			{
				dsu.MakeSet(platform, j);
				if (j && a[platform][j - 1] == 1)
					dsu.Union(platform, j, platform, j - 1);
				else
					plats.push_back(make_pair(platform, j));
			}
		}
	else if (dsu_.Count())
	{
		hard = true;
		dsu.SetHard(dsu_);
	}
	upds_.clear();
	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')
					{
						if (!hard)
							TryPlatUnion(plats, dsu, upds_, i, j, i1, j1, i - l);
						dsu.Union(i, j, i1, j1);
					}
				}
			}
		// cerr << "**************dsu size: " << dsu.Count() << endl;
		res += dsu.Count();
	}
	/*
	char I;
	cin >> I;
	*/
	return res;
}
int SuffAns(int l, int r, int platform = -1, Dsu dsu_ = Dsu())
{
	int res = 0;
	Dsu dsu;
	vector< pair<int, int> > plats;
	bool hard = false;
	if (platform != -1)
		for (int j = 0; j < m; ++j)
		{
			if (a[platform][j] == 1)
			{
				dsu.MakeSet(platform, j);
				if (j && a[platform][j - 1] == 1)
					dsu.Union(platform, j, platform, j - 1);
				else
					plats.push_back(make_pair(platform, j));
			}
		}
	else if (dsu_.Count())
	{
		hard = true;
		dsu.SetHard(dsu_);
	}
	if (l == 0 && r == 0 && hard)
		cerr << "";
	upds_.clear();
	for (int i = r; i >= l; --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 >= i && (i1 <= r || (i1 == r + 1 && (hard || platform != -1))) && j1 >= 0 && j1 < m && a[i1][j1] == '1')
					{
						if (!hard)
							TryPlatUnion(plats, dsu, upds_, i, j, i1, j1, r - i);
						dsu.Union(i, j, i1, j1);
					}
				}
			}
		// cerr << "**************dsu size: " << dsu.Size() << endl;
		res += dsu.Count();
	}
	/*
	char I;
	cin >> I;
	*/
	return res;
}
int Solve(int vl, int vr)
{
	if (vl == vr)
		return PrefAns(vl, vr);
	int vm = vl + (vr - vl) / 2;
	int ans = Solve(vl, vm) + Solve(vm + 1, vr);
	SuffAns(vl, vm, vm + 1);
	vector<PlatUnion> upds;
	upds.swap(upds_);
	upds.push_back(PlatUnion(vm - vl + 1, -1, -1, -1, -1));
	Dsu dsu;
	for (int j = 0; j < m; ++j)
		if (a[vm][j] == '1')
		{
			dsu.MakeSet(vm, j);
			if (j && a[vm][j - 1] == '1')
				dsu.Union(vm, j, vm, j - 1);
		}
	for (auto upd = upds.begin(); upd != upds.end(); ++upd)
	{
		if (next(upd) != upds.end())
			dsu.Union(upd->i1, upd->j1, upd->i2, upd->j2);
		ans += (upd->after - (upd == upds.begin() ? 0 : std::prev(upd)->after)) * PrefAns(vm + 1, vr, -1, dsu);
	}
	PrefAns(vm + 1, vr, vm);
	upds.swap(upds_);
	upds.push_back(PlatUnion(vr - vm, -1, -1, -1, -1));
	dsu = Dsu();
	for (int j = 0; j < m; ++j)
		if (a[vm + 1][j] == '1')
		{
			dsu.MakeSet(vm + 1, j);
			if (j && a[vm + 1][j - 1] == '1')
				dsu.Union(vm + 1, j, vm + 1, j - 1);
		}
	for (auto upd = upds.begin(); upd != upds.end(); ++upd)
	{
		if (next(upd) != upds.end())
			dsu.Union(upd->i1, upd->j1, upd->i2, upd->j2);
		ans += (upd->after - (upd == upds.begin() ? 0 : std::prev(upd)->after)) * SuffAns(vl, vm, -1, dsu);
	}
	// ans -= (PrefAns(vm, vm + 1) + PrefAns(vm + 1, vm + 1));
	// ans += (vm - vl + 1) * PrefAns(vm + 1, vr);
	// ans += (vr - vm) * SuffAns(vl, vm);
	cout << "Solve(" << vl << ", " << vr << ") returns " << ans << endl;
	return ans;
}
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 += SuffAns(0, i);
	cout << ans << endl;
	*/
	cout <<	Solve(0, n - 1) << endl;

	char I;
	cin >> I;
}

Compilation message (stderr)

raspad.cpp: In constructor 'Dsu::Dsu()':
raspad.cpp:69:6: warning: 'Dsu::count' will be initialized after [-Wreorder]
  int count;
      ^~~~~
raspad.cpp:67:7: warning:   'bool Dsu::hard' [-Wreorder]
  bool hard;
       ^~~~
raspad.cpp:28:2: warning:   when initialized here [-Wreorder]
  Dsu()
  ^~~
raspad.cpp: In function 'void TryPlatUnion(std::vector<std::pair<int, int> >&, Dsu, std::vector<PlatUnion>&, int, int, int, int, int)':
raspad.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < plats.size(); ++i)
                  ~~^~~~~~~~~~~~~~

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