Submission #1003982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003982		vjudge1	Paint (COI20_paint)	C++17	48 / 100	3022 ms	69748 KiB

paint

#include <bits/stdc++.h>
using namespace std;
vector<int> sub, isHeavy, cor, pai;
vector<unordered_set<int>> grafoLight;
vector<vector<unordered_set<int>>> grafoHeavy;
unordered_set<int> idHeavies;
const int MAXV = 1e5;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int R, S;
int T;

int find(int v) {return pai[v] = (v == pai[v] ? v : find(pai[v]));}
void une(int x, int y)
{
	x = find(x); y = find(y);
	if (x == y) return;
	if (sub[x] < sub[y]) swap(sub[x], sub[y]);
	pai[y] = x; sub[x] += sub[y];
	for (auto viz : grafoLight[y]) grafoLight[find(viz)].erase(y), grafoLight[find(viz)].insert(x);
	
	if (isHeavy[x] && isHeavy[y])
	{
		for (int c = 0; c < MAXV; c++)
			for (auto viz : grafoHeavy[y][c])
				grafoHeavy[x][c].insert(viz);
		grafoHeavy[y].clear();
		idHeavies.erase(y);
	}
	else if (isHeavy[x])
	{
		for (auto viz : grafoLight[y]) grafoHeavy[x][cor[viz]].insert(viz);
	}
	else if (isHeavy[y])
	{
		isHeavy[x] = 1;
		swap(grafoHeavy[x], grafoHeavy[y]);
		for (auto viz : grafoLight[x]) grafoHeavy[x][cor[viz]].insert(viz);
		idHeavies.insert(x); idHeavies.erase(y);
	}
	else if (grafoLight[x].size() > T)
	{
		isHeavy[x] = 1;
		idHeavies.insert(x);
		grafoHeavy[x].resize(MAXV);
		for (auto viz : grafoLight[x]) if (find(viz) != x) grafoHeavy[x][cor[viz]].insert(viz);
	}

	if (grafoLight[x].size() < grafoLight[y].size()) swap(grafoLight[x], grafoLight[y]);
	for (auto viz : grafoLight[y]) grafoLight[x].insert(find(viz));
	grafoLight[y].clear();
}

int getId(int x, int y) {return x*S + y;}
void getUnion(int i, int j, int C = -1)
{
	// cerr << "||" << getId(i, j) << " (" << i << ", " << j << ")" << '\n';
	int id = find(getId(i, j));
	int lastC = cor[id];
	if (C != -1) cor[id] = C;
	else C = cor[id];

	vector<int> viz;
	if (isHeavy[id]) 
	{
		while (!grafoHeavy[id][C].empty())
		{
			int x = *grafoHeavy[id][C].begin(); grafoHeavy[id][C].erase(grafoHeavy[id][C].begin());
			une(id, x);
			id = find(id);
		}
	}
	else
		for (auto x : grafoLight[id]) if (cor[find(x)] == C) viz.push_back(find(x));
	
	for (auto x : viz) une(id, x);

	for (auto x : grafoLight[find(id)]) if (isHeavy[find(x)])
	{
		grafoHeavy[find(x)][lastC].erase(find(id));
		grafoHeavy[find(x)][C].insert(find(id));
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> R >> S;
	vector<vector<int>> mat(R, vector<int>(S));
	for (auto &x : mat)
		for (auto &y : x)
			cin >> y;

	T = (int)1e9;
	pai.resize(R*S); iota(pai.begin(), pai.end(), 0);
	sub.resize(R*S); fill(sub.begin(), sub.end(), 1);
	isHeavy.resize(R*S, 0); 
	cor.resize(R*S); for (int i = 0; i < R; i++) for (int j = 0; j < S; j++) cor[getId(i, j)] = mat[i][j];
	grafoLight.resize(R*S); grafoHeavy.resize(R*S);
	for (int i = 0; i < R; i++)
		for (int j = 0; j < S; j++)
		{
			for (int k = 0; k < 4; k++)
			{
				int hx = i + dx[k];
				int hy = j + dy[k];
				if (hx < 0 || hx >= R || hy < 0 || hy >= S) continue;
				grafoLight[getId(i, j)].insert(getId(hx, hy));
			}
		}

	for (int i = 0; i < R; i++)
		for (int j = 0; j < S; j++)
		{
			getUnion(i, j);
		}

	// cerr << "Start queries" << '\n';
	int Q; cin >> Q;
	while (Q--)
	{
		int X, Y, C;
		cin >> X >> Y >> C;
		--X, --Y;
		getUnion(X, Y, C);
	}

	for (int i = 0; i < R; i++) for (int j = 0; j < S; j++) mat[i][j] = cor[find(getId(i, j))];
	for (auto &x : mat)
	{
		for (auto y : x)
			cout << y << " ";
		cout << '\n';
	}
}

Compilation message (stderr)

paint.cpp: In function 'void une(int, int)':
paint.cpp:41:32: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |  else if (grafoLight[x].size() > T)
      |           ~~~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 31 / 31
• Subtask 4: 0 / 52