#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
const int B = 500;
vector<int> sz, p;
vector<int> clr;
vector<unordered_set<int> > g;
vector<vector<unordered_set<int> > > big_g;
vector<unordered_set<int> > big;
int get_par(int a)
{
if (p[a] == a)
return a;
return p[a] = get_par(p[a]);
}
void mrg(int a, int b)
{
a = get_par(a);
b = get_par(b);
if (a != b)
{
if (sz[a] < sz[b])
swap(a, b);
sz[a] += sz[b];
p[b] = a;
}
}
const int MAXC = 1e5 + 1;
void bigock(int a, int b)
{
if (sz[a] < sz[b])
swap(a, b);
if (sz[b] < B)
{
for (auto& u : g[b])
{
int v = get_par(u);
big_g[a][clr[v]].insert(v);
big[v].insert(a);
}
}
else
{
for (int c = 0; c < MAXC; c++)
{
for (auto& u : big_g[b][c])
{
big_g[a][c].insert(u);
}
}
}
mrg(a, b);
for (auto& u : big[b])
{
big[a].insert(u);
}
}
void add_bigock(int a)
{
big_g[a].resize(MAXC + 1);
for (auto& u : g[a])
{
big[get_par(u)].insert(a);
big_g[a][clr[get_par(u)]].insert(u);
}
}
void smallock(int a, int b)
{
if (sz[a] < sz[b])
swap(a, b);
mrg(a, b);
for (auto& u : g[b])
{
g[a].insert(get_par(u));
}
for (auto& u : big[b])
{
big[a].insert(get_par(u));
}
if (sz[a] >= B)
{
add_bigock(a);
}
}
void mrge(int a, int b)
{
a = get_par(a);
b = get_par(b);
if (a == b) return;
if (max(sz[a], sz[b]) >= B)
{
bigock(a, b);
}
else
{
smallock(a, b);
}
}
pair<int, int> delta[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void solve()
{
int n, m;
cin >> n >> m;
g.resize(n * m);
sz.resize(n * m, 1);
p.resize(n * m);
iota(p.begin(), p.end(), 0);
clr.resize(n * m);
vector<vector<int> > field(n, vector<int>(m));
auto get_id = [&](int x, int y)
{
return x * m + y;
};
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> field[i][j];
clr[get_id(i, j)] = field[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
for (auto&[dx, dy] : delta)
{
int nx = i + dx, ny = j + dy;
if (nx >= 0 && nx < n && ny >= 0 && ny < m)
{
if (field[i][j] == field[nx][ny])
{
mrg(get_id(i, j), get_id(nx, ny));
}
}
}
}
}
big.resize(n * m);
big_g.resize(n * m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
for (auto&[dx, dy] : delta)
{
int nx = i + dx, ny = j + dy;
if (nx >= 0 && nx < n && ny >= 0 && ny < m)
{
if (field[i][j] != field[nx][ny])
{
g[get_par(get_id(i, j))].insert({get_par(get_id(nx, ny))});
}
}
}
}
}
for (int i = 0; i < n * m; i++)
{
if (get_par(i) == i && sz[i] >= B)
{
big_g[i].resize(MAXC + 1);
for (auto& u : g[i])
{
big[u].insert(i);
big_g[i][clr[u]].insert(u);
}
}
}
int q;
cin >> q;
for (int i = 0; i < q; i++)
{
int r, s, c;
cin >> r >> s >> c;
r--; s--;
int v = get_par(get_id(r, s));
clr[v] = c;
if (sz[v] >= B)
{
auto bg = big_g[v][c];
big_g[v][c].clear();
for (auto& u : bg)
{
if (get_par(u) != get_par(v) && clr[get_par(u)] == c)
{
mrge(v, u);
}
}
}
else
{
for (auto& u : g[v])
{
if (get_par(u) != get_par(v) && clr[get_par(u)] == c)
{
mrge(u, v);
}
}
}
for (auto& u : big[get_par(v)])
{
big_g[get_par(u)][clr[get_par(v)]].insert(get_par(v));
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cout << clr[get_par(get_id(i, j))] << " ";
}
cout << '\n';
}
return;
}
signed main()
{
//ifstream cin("input.txt");
//ofstream cout("output.txt");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//assert(mx <= 4);
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
/*
1
1000000000000000000
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
712 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
78 ms |
17592 KB |
Output is correct |
| 2 |
Incorrect |
323 ms |
338272 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
177 ms |
101832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
179 ms |
68336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
