| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1003789 |
2024-06-20T17:50:43 Z |
vjudge1 |
Paint (COI20_paint) |
C++17 |
|
3000 ms |
33864 KB |
#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
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)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1372 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1556 KB |
Output is correct |
| 5 |
Correct |
1627 ms |
1924 KB |
Output is correct |
| 6 |
Correct |
2391 ms |
2272 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
6804 KB |
Output is correct |
| 2 |
Correct |
522 ms |
15816 KB |
Output is correct |
| 3 |
Execution timed out |
3074 ms |
21312 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1737 ms |
32388 KB |
Output is correct |
| 2 |
Correct |
1235 ms |
33468 KB |
Output is correct |
| 3 |
Correct |
1594 ms |
33864 KB |
Output is correct |
| 4 |
Execution timed out |
3059 ms |
30168 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
423 ms |
20920 KB |
Output is correct |
| 2 |
Execution timed out |
3013 ms |
24452 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
