oj.uz

Submission #1003987

# Submission time Handle Problem Language Result Execution time Memory
1003987 2024-06-20T21:14:34 Z vjudge1 Paint (COI20_paint) C++17
48 / 100
 3000 ms 69744 KB 
#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 + 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)].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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 6 ms 3796 KB Output is correct
4 Correct 9 ms 3160 KB Output is correct
5 Correct 746 ms 3800 KB Output is correct
6 Correct 17 ms 3676 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 15244 KB Output is correct
2 Correct 94 ms 28604 KB Output is correct
3 Correct 118 ms 57668 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 67924 KB Output is correct
2 Correct 191 ms 68028 KB Output is correct
3 Correct 205 ms 67408 KB Output is correct
4 Correct 336 ms 65792 KB Output is correct
5 Correct 209 ms 62548 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 50520 KB Output is correct
2 Execution timed out 3031 ms 69744 KB Time limit exceeded
3 Halted 0 ms 0 KB -