#include <bits/stdc++.h>
using namespace std;
void debug(set<int>& s) {
cout << "[";
for (auto it=s.begin(); it!=s.end(); ++it) {
cout << *it;
if (next(it)!=s.end())
cout << ", ";
}
cout << "]" << endl;
}
#define ar array
const int mxN=2e5, B=47000; // component is considered large if size>=B
const int dx[4]={1, -1, 0, 0}, dy[4]={0, 0, 1, -1};
const bool dbg=0; // change
int p[mxN];
struct Component {
int color;
bool large;
vector<ar<int, 2>> pixels;
set<int> small_neighbors, big_neighbors;
map<int, set<int>> by_color;
int size() {
return pixels.size();
}
} components[mxN];
int find(int i) {
return i^p[i]?p[i]=find(p[i]):i;
}
void declare_large(int u) {
assert(u==find(u)&&!components[u].large);
components[u].large=1;
for (int v : components[u].small_neighbors) {
assert(v==find(v));
components[u].by_color[components[v].color].insert(v);
components[v].big_neighbors.insert(u);
}
set<int>().swap(components[u].small_neighbors);
}
void mrg(int u, int v) {
if (dbg)
cout << "merging " << u << " " << v << endl;
int color=components[u].color;
assert(u==find(u)&&v==find(v)&&color==components[v].color);
if (components[u].size()<components[v].size())
swap(u, v);
assert(components[u].large>=components[v].large);
for (ar<int, 2> x : components[v].pixels)
components[u].pixels.push_back(x);
vector<ar<int, 2>>().swap(components[v].pixels);
if (components[u].size()+components[v].size()>=B) { // new component is large, merge them
if (!components[u].large)
declare_large(u);
if (!components[v].large)
declare_large(v);
for (int rep=0; rep<2; ++rep) {
auto it=components[u].by_color.find(color);
assert(it!=components[u].by_color.end());
auto it2=it->second.find(v);
assert(it2!=it->second.end());
it->second.erase(it2);
if (it->second.empty())
components[u].by_color.erase(color);
swap(u, v);
}
for (auto& x : components[v].by_color) // move by_color
for (int y : x.second) {
assert(y==find(y));
if (components[y].large) {
components[y].by_color[color].erase(v);
components[y].by_color[color].insert(u);
} else {
components[y].small_neighbors.erase(v);
components[y].small_neighbors.insert(u);
}
components[y].big_neighbors.erase(v);
components[y].big_neighbors.insert(u);
components[u].by_color[x.first].insert(y);
}
map<int, set<int>>().swap(components[v].by_color);
} else { // both are still small
for (int rep=0; rep<2; ++rep) {
auto it=components[u].small_neighbors.find(v);
assert(it!=components[u].small_neighbors.end());
components[u].small_neighbors.erase(it);
swap(u, v);
}
for (int x : components[v].small_neighbors) {
assert(x==find(x));
if (components[x].large) {
components[x].by_color[color].erase(v);
components[x].by_color[color].insert(u);
} else {
components[x].small_neighbors.erase(v);
components[x].small_neighbors.insert(u);
}
components[u].small_neighbors.insert(x);
}
set<int>().swap(components[v].small_neighbors);
if (dbg) {
cout << "small_neighbors of " << u << ":";
debug(components[u].small_neighbors);
}
}
p[v]=u;
for (int x : components[v].big_neighbors)
components[u].big_neighbors.insert(x);
set<int>().swap(components[v].big_neighbors);
components[u].big_neighbors.erase(u);
components[u].big_neighbors.erase(v);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
for (vector<int>& v : grid)
for (int& i : v)
cin >> i;
vector<vector<int>> vis(n, vector<int>(m, -1));
int cc=0; // component counter
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j) {
if (vis[i][j]!=-1)
continue;
queue<ar<int, 2>> q;
q.push({i, j});
vis[i][j]=cc;
vector<ar<int, 2>> pixels;
while(q.size()) {
int i=q.front()[0], j=q.front()[1];
q.pop();
pixels.push_back({i, j});
for (int k=0; k<4; ++k) {
int ni=i+dx[k], nj=j+dy[k];
if (0<=ni&&ni<n&&0<=nj&&nj<m&&vis[ni][nj]==-1&&grid[i][j]==grid[ni][nj]) {
q.push({ni, nj});
vis[ni][nj]=cc;
}
}
}
components[cc].color=grid[i][j];
components[cc].pixels=pixels;
p[cc]=cc;
++cc;
}
if (dbg)
cout << endl;
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
if (i+1<n&&grid[i][j]!=grid[i+1][j]) {
components[vis[i][j]].small_neighbors.insert(vis[i+1][j]);
components[vis[i+1][j]].small_neighbors.insert(vis[i][j]);
}
if (j+1<m&&grid[i][j]!=grid[i][j+1]) {
components[vis[i][j]].small_neighbors.insert(vis[i][j+1]);
components[vis[i][j+1]].small_neighbors.insert(vis[i][j]);
}
if (dbg)
cout << vis[i][j] << " ";
}
if (dbg)
cout << endl;
}
/*for (int i=0; i<cc; ++i) {
clean(components[i].small_neighbors);
cout << i << " :";
for (int j : v)
cout << " " << j;
cout << endl;
}*/
for (int i=0; i<cc; ++i)
if (components[i].size()>=B)
declare_large(i);
//cout << "REACHED" << endl;
int q;
cin >> q;
while(q--) {
int i, j, c;
cin >> i >> j >> c, --i, --j;
int u=find(vis[i][j]); // what is the actual component
int last_color=components[u].color;
components[u].color=c;
for (int v : components[u].big_neighbors) { // they need to know that color of this component has changed
assert(v==find(v));
/*if (v!=find(v)) {
cout << u << " " << v << endl;
return 0;
}*/
//v=find(v);
components[v].by_color[last_color].erase(u);
if (components[v].by_color[last_color].empty())
components[v].by_color.erase(last_color);
components[v].by_color[c].insert(u);
}
vector<int> cands;
if (!components[u].large) { // small
for (int i : components[u].small_neighbors) {
assert(i==find(i));
cands.push_back(i);
}
} else {
if (components[u].by_color.find(c)!=components[u].by_color.end()) {
//debug(components[u].by_color[c]);
for (int i : components[u].by_color[c]) {
assert(i==find(i));
cands.push_back(i);
}
//components[u].by_color.erase(c);
}
}
//vector<int> cands=components[u].large?components[u].by_color[c]:components[u].small_neighbors;
for (int v : cands) {
if (find(v)!=u&&components[find(v)].color==c) {
mrg(u, find(v));
u=find(u);
}
}
if (dbg&&components[u].by_color.find(c)!=components[u].by_color.end()) {
cout << u << " : ";
debug(components[u].by_color[c]);
}
assert(components[u].by_color.find(c)==components[u].by_color.end());
//if (components[u].large)
//components[u].by_color.erase(c);
}
vector<vector<int>> ans(n, vector<int>(m));
for (int i=0; i<cc; ++i)
if (i==find(i))
for (ar<int, 2> x : components[i].pixels)
ans[x[0]][x[1]]=components[i].color;
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j)
cout << ans[i][j] << " ";
cout << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
34888 KB |
Output is correct |
| 2 |
Correct |
20 ms |
34900 KB |
Output is correct |
| 3 |
Correct |
26 ms |
36952 KB |
Output is correct |
| 4 |
Correct |
28 ms |
36464 KB |
Output is correct |
| 5 |
Correct |
107 ms |
36024 KB |
Output is correct |
| 6 |
Correct |
26 ms |
36224 KB |
Output is correct |
| 7 |
Correct |
17 ms |
34648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
41484 KB |
Output is correct |
| 2 |
Correct |
157 ms |
46444 KB |
Output is correct |
| 3 |
Correct |
171 ms |
55436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
340 ms |
82156 KB |
Output is correct |
| 2 |
Correct |
321 ms |
81708 KB |
Output is correct |
| 3 |
Correct |
336 ms |
82724 KB |
Output is correct |
| 4 |
Correct |
411 ms |
80604 KB |
Output is correct |
| 5 |
Correct |
322 ms |
77196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
328 ms |
64848 KB |
Output is correct |
| 2 |
Correct |
553 ms |
76436 KB |
Output is correct |
| 3 |
Correct |
1143 ms |
63512 KB |
Output is correct |
| 4 |
Correct |
2614 ms |
60364 KB |
Output is correct |
| 5 |
Correct |
2923 ms |
66336 KB |
Output is correct |
| 6 |
Correct |
2369 ms |
62764 KB |
Output is correct |
| 7 |
Correct |
2091 ms |
55864 KB |
Output is correct |
| 8 |
Correct |
2043 ms |
51308 KB |
Output is correct |
| 9 |
Correct |
2916 ms |
67432 KB |
Output is correct |
