Boj 14258) Xor 그룹

UnionFind

백준 14258

설명

하나하나 빼가는걸 역순으로 하면 UnionFind 문제가 됨.

주의사항은 1부터 1,000,000 까지 대충 더하면 int 범위 넘는다는 것.

시간 복잡도

O(\(\alpha(N)N\))

코드

using INT = int64_t;
INT board[1002 * 1002];

#define INTMAX 1000001
INT cycleTB[INTMAX];
INT xorTB[INTMAX];
INT Root(INT i)
{
	if (i == cycleTB[i]) return i;
	return cycleTB[i] = Root(cycleTB[i]);
}

void Union(INT i, INT j, INT& cur)
{
	i = Root(i);
	j = Root(j);
	if (i == j) return;
	cycleTB[max(i, j)] = min(i, j);

	cur -= xorTB[i];
	cur -= xorTB[j];
	cur += xorTB[min(i, j)] ^= xorTB[max(i, j)];
}

int main()
{
	fastio;

	INT m, n;
	cin >> m >> n;
	
	for (INT i = 0; i <= INTMAX; i++)
		cycleTB[i] = i;
	
	using P = pair<INT, INT>;
	vector<P> erase_list;
	erase_list.reserve(m * n);
	
	for (INT i = 0; i < m; i++)
		for (INT j = 0; j < n; j++)
		{
			static INT tmp;
			tmp = i * n + j;
			cin >> board[tmp];
			erase_list.push_back({ board[tmp], tmp });
		}
	
	sort(erase_list.begin(), erase_list.end(), [](const P& a, const P& b) { return a.first > b.first; });
	
	INT ans = 0, cur = 0;
	for (const auto& l : erase_list)
	{
		INT x = l.second % n;
		INT y = l.second / n;
	
		cur += xorTB[l.first] = l.first;			
	
		if (x - 1 >= 0 && xorTB[board[y * n + x - 1]])
			Union(l.first, board[y * n + x - 1], cur);
		if (x + 1 < n && xorTB[board[y * n + x + 1]])
			Union(l.first, board[y * n + x + 1], cur);
		if (y - 1 >= 0 && xorTB[board[(y - 1) * n + x]])
			Union(l.first, board[(y - 1) * n + x], cur);
		if (y + 1 < m && xorTB[board[(y + 1) * n + x]])
			Union(l.first, board[(y + 1) * n + x], cur);
	
		ans = max(ans, cur);
	}
	
	cout << ans;
}