| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1003968 |
2024-06-20T21:01:02 Z |
vjudge1 |
Paint (COI20_paint) |
C++17 |
|
3000 ms |
80992 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 = sqrt(3*R*S)+1;
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)
| ~~~~~~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
2 ms |
856 KB |
Output is correct |
| 3 |
Correct |
8 ms |
3800 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
8540 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
14732 KB |
Output is correct |
| 2 |
Correct |
120 ms |
28396 KB |
Output is correct |
| 3 |
Correct |
148 ms |
56644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
223 ms |
67928 KB |
Output is correct |
| 2 |
Correct |
213 ms |
68000 KB |
Output is correct |
| 3 |
Correct |
266 ms |
67264 KB |
Output is correct |
| 4 |
Correct |
287 ms |
65872 KB |
Output is correct |
| 5 |
Correct |
229 ms |
62596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
246 ms |
56140 KB |
Output is correct |
| 2 |
Execution timed out |
3011 ms |
80992 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
