Submission #1003789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003789		vjudge1	Paint (COI20_paint)	C++17	8 / 100	3074 ms	33864 KiB

paint

#include <bits/stdc++.h>
using namespace std;
vector<int> sub, isHeavy, cor, pai;
vector<vector<int>> grafoLight;
vector<vector<set<int>>> grafoHeavy;
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;
	// cerr << "une " << x << " (" << x/S << ", " << x%S << ") and " << y << " (" << y/S << ", " << y%S << ")" << '\n';
	if (sub[x] < sub[y]) swap(sub[x], sub[y]);
	pai[y] = x; sub[x] += sub[y];
	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]) if (cor[find(viz)] != cor[x]) grafoHeavy[x][cor[viz]].insert(viz);
		grafoLight[y].clear();
	}
	else if (isHeavy[y])
	{
		isHeavy[x] = 1;
		swap(grafoHeavy[x], grafoHeavy[y]);
		for (auto viz : grafoLight[x]) if (cor[find(viz)] != cor[x]) grafoHeavy[x][cor[viz]].insert(viz);
		grafoLight[x].clear(); idHeavies.insert(x); idHeavies.erase(y);
	}
	else if (grafoLight[x].size() + grafoLight[y].size() > T)
	{
		isHeavy[x] = 1;
		idHeavies.insert(x);
		grafoHeavy[x].resize(MAXV);
		for (auto viz : grafoLight[x]) if (cor[find(viz)] != cor[x]) grafoHeavy[x][cor[viz]].insert(viz);
		for (auto viz : grafoLight[y]) if (cor[find(viz)] != cor[x]) grafoHeavy[x][cor[viz]].insert(viz);
		grafoLight[x].clear(); grafoLight[y].clear();
	}
	else
	{
		if (grafoLight[x].size() < grafoLight[y].size()) swap(grafoLight[x], grafoLight[y]);
		for (auto viz : grafoLight[y]) grafoLight[x].push_back(viz);
	}
}

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];
	if (isHeavy[id]) 
	{
		// cerr << "\tHeavy" << '\n';
		while (!grafoHeavy[id][cor[id]].empty())
		{
			auto it = grafoHeavy[id][cor[id]].begin();
			int x = *it; grafoHeavy[id][cor[id]].erase(it);
			x = find(x);
			if (cor[x] == cor[id]) une(id, x);
		}
	}
	else
	{
		// cerr << "\tLight" << '\n';
		vector<int> viz;
		for (auto x : grafoLight[id]) if (cor[find(x)] == cor[id]) viz.push_back(find(x));
		for (auto x : viz) une(id, x);
		// id = find(id); cerr << "new id: " << id << '\n';
	}

	id = find(id);
	if (!isHeavy[id])
	{
		for (auto x : grafoLight[id]) 
		{
			if (isHeavy[find(x)]) 
			{
				// cerr << "x: " << find(x) << '\n';
				grafoHeavy[find(x)][lastC].erase(id), grafoHeavy[find(x)][C].insert(id);
			}
		}
	}
	else
	{
		for (auto x : idHeavies)
		{
			if (x != id && grafoHeavy[x][lastC].count(id))
				grafoHeavy[x][lastC].erase(id), grafoHeavy[x][C].insert(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)4e5 + 10;
	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)].push_back(getId(hx, hy));
			}
		}

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

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

	// 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:55: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |  else if (grafoLight[x].size() + grafoLight[y].size() > T)
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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