This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define si set<int>
#define vi vector<int>
#define ER ER
#define IN IN
const int mxN=2e5, B=700;
const int dx[4]={1, -1, 0, 0}, dy[4]={0, 0, 1, -1};
int p[mxN];
struct CP {
int sz, color;
bool lg;
si sn, bn;
unordered_map<int, si> bc;
} cp[mxN];
int find(int i) {
return i^p[i]?p[i]=find(p[i]):i;
}
void de(int u) {
cp[u].lg=1;
for (int v : cp[u].sn) {
cp[u].bc[cp[v].color].IN(v);
cp[v].bn.IN(u);
}
si().swap(cp[u].sn);
}
void mrg(int u, int v) {
CP& X=cp[u];
CP& Y=cp[v];
int color=X.color;
if (X.sz<Y.sz)
swap(u, v);
if (X.sz+Y.sz>=B) {
if (!X.lg)
de(u);
if (!Y.lg)
de(v);
for (int rep=0; rep<2; ++rep) {
auto it=X.bc.find(color);
auto it2=it->second.find(v);
it->second.ER(it2);
if (it->second.empty())
X.bc.ER(color);
swap(u, v);
}
for (auto& x : Y.bc)
for (int y : x.second) {
if (cp[y].lg) {
cp[y].bc[color].ER(v);
cp[y].bc[color].IN(u);
} else {
cp[y].sn.ER(v);
cp[y].sn.IN(u);
}
cp[y].bn.ER(v);
cp[y].bn.IN(u);
X.bc[x.first].IN(y);
}
unordered_map<int, si>().swap(Y.bc);
} else {
for (int rep=0; rep<2; ++rep) {
auto it=X.sn.find(v);
X.sn.ER(it);
swap(u, v);
}
for (int x : Y.sn) {
if (cp[x].lg) {
cp[x].bc[color].ER(v);
cp[x].bc[color].IN(u);
} else {
cp[x].sn.ER(v);
cp[x].sn.IN(u);
}
X.sn.IN(x);
}
si().swap(Y.sn);
}
p[v]=u;
for (int x : Y.bn)
X.bn.IN(x);
si().swap(Y.bn);
X.bn.ER(u);
X.bn.ER(v);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vi> grid(n, vi(m));
for (vi& v : grid)
for (int& i : v)
cin >> i;
vector<vi> vis(n, vi(m, -1));
int cc=0;
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;
int sz=0;
while(q.size()) {
int i=q.front()[0], j=q.front()[1];
q.pop();
++sz;
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;
}
}
}
cp[cc].sz=sz;
cp[cc].color=grid[i][j];
p[cc]=cc;
++cc;
}
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]) {
cp[vis[i][j]].sn.IN(vis[i+1][j]);
cp[vis[i+1][j]].sn.IN(vis[i][j]);
}
if (j+1<m&&grid[i][j]!=grid[i][j+1]) {
cp[vis[i][j]].sn.IN(vis[i][j+1]);
cp[vis[i][j+1]].sn.IN(vis[i][j]);
}
}
for (int i=0; i<cc; ++i)
if (cp[i].sz>=B)
de(i);
int q;
cin >> q;
while(q--) {
int i, j, c;
cin >> i >> j >> c, --i, --j;
int u=find(vis[i][j]);
int lc=cp[u].color;
cp[u].color=c;
for (int v : cp[u].bn) {
cp[v].bc[lc].ER(u);
if (cp[v].bc[lc].empty())
cp[v].bc.ER(lc);
cp[v].bc[c].IN(u);
}
vi cands;
if (!cp[u].lg) { // small
for (int i : cp[u].sn)
cands.push_back(i);
} else {
if (cp[u].bc.find(c)!=cp[u].bc.end())
for (int i : cp[u].bc[c])
cands.push_back(i);
}
for (int v : cands) {
if (find(v)!=u&&cp[find(v)].color==c) {
mrg(u, find(v));
u=find(u);
}
}
}
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j)
cout << cp[find(vis[i][j])].color << " ";
cout << "\n";
}
return 0;
}
Compilation message (stderr)
paint.cpp: In function 'void de(int)':
paint.cpp:8:12: error: 'std::unordered_map<int, std::set<int> >::mapped_type' {aka 'class std::set<int>'} has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:28:23: note: in expansion of macro 'IN'
28 | cp[u].bc[cp[v].color].IN(v);
| ^~
paint.cpp:8:12: error: 'class std::set<int>' has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:29:10: note: in expansion of macro 'IN'
29 | cp[v].bn.IN(u);
| ^~
paint.cpp: In function 'void mrg(int, int)':
paint.cpp:7:12: error: 'class std::set<int>' has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:48:12: note: in expansion of macro 'ER'
48 | it->second.ER(it2);
| ^~
paint.cpp:7:12: error: 'class std::unordered_map<int, std::set<int> >' has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:50:6: note: in expansion of macro 'ER'
50 | X.bc.ER(color);
| ^~
paint.cpp:7:12: error: 'std::unordered_map<int, std::set<int> >::mapped_type' {aka 'class std::set<int>'} has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:56:17: note: in expansion of macro 'ER'
56 | cp[y].bc[color].ER(v);
| ^~
paint.cpp:8:12: error: 'std::unordered_map<int, std::set<int> >::mapped_type' {aka 'class std::set<int>'} has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:57:17: note: in expansion of macro 'IN'
57 | cp[y].bc[color].IN(u);
| ^~
paint.cpp:7:12: error: 'class std::set<int>' has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:59:10: note: in expansion of macro 'ER'
59 | cp[y].sn.ER(v);
| ^~
paint.cpp:8:12: error: 'class std::set<int>' has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:60:10: note: in expansion of macro 'IN'
60 | cp[y].sn.IN(u);
| ^~
paint.cpp:7:12: error: 'class std::set<int>' has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:62:10: note: in expansion of macro 'ER'
62 | cp[y].bn.ER(v);
| ^~
paint.cpp:8:12: error: 'class std::set<int>' has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:63:10: note: in expansion of macro 'IN'
63 | cp[y].bn.IN(u);
| ^~
paint.cpp:8:12: error: 'std::unordered_map<int, std::set<int> >::mapped_type' {aka 'class std::set<int>'} has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:65:15: note: in expansion of macro 'IN'
65 | X.bc[x.first].IN(y);
| ^~
paint.cpp:7:12: error: 'class std::set<int>' has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:71:6: note: in expansion of macro 'ER'
71 | X.sn.ER(it);
| ^~
paint.cpp:7:12: error: 'std::unordered_map<int, std::set<int> >::mapped_type' {aka 'class std::set<int>'} has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:76:17: note: in expansion of macro 'ER'
76 | cp[x].bc[color].ER(v);
| ^~
paint.cpp:8:12: error: 'std::unordered_map<int, std::set<int> >::mapped_type' {aka 'class std::set<int>'} has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:77:17: note: in expansion of macro 'IN'
77 | cp[x].bc[color].IN(u);
| ^~
paint.cpp:7:12: error: 'class std::set<int>' has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:79:10: note: in expansion of macro 'ER'
79 | cp[x].sn.ER(v);
| ^~
paint.cpp:8:12: error: 'class std::set<int>' has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:80:10: note: in expansion of macro 'IN'
80 | cp[x].sn.IN(u);
| ^~
paint.cpp:8:12: error: 'class std::set<int>' has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:82:6: note: in expansion of macro 'IN'
82 | X.sn.IN(x);
| ^~
paint.cpp:8:12: error: 'class std::set<int>' has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:88:6: note: in expansion of macro 'IN'
88 | X.bn.IN(x);
| ^~
paint.cpp:7:12: error: 'class std::set<int>' has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:90:6: note: in expansion of macro 'ER'
90 | X.bn.ER(u);
| ^~
paint.cpp:7:12: error: 'class std::set<int>' has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:91:6: note: in expansion of macro 'ER'
91 | X.bn.ER(v);
| ^~
paint.cpp: In function 'int main()':
paint.cpp:8:12: error: 'class std::set<int>' has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:133:18: note: in expansion of macro 'IN'
133 | cp[vis[i][j]].sn.IN(vis[i+1][j]);
| ^~
paint.cpp:8:12: error: 'class std::set<int>' has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:134:20: note: in expansion of macro 'IN'
134 | cp[vis[i+1][j]].sn.IN(vis[i][j]);
| ^~
paint.cpp:8:12: error: 'class std::set<int>' has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:137:18: note: in expansion of macro 'IN'
137 | cp[vis[i][j]].sn.IN(vis[i][j+1]);
| ^~
paint.cpp:8:12: error: 'class std::set<int>' has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:138:20: note: in expansion of macro 'IN'
138 | cp[vis[i][j+1]].sn.IN(vis[i][j]);
| ^~
paint.cpp:7:12: error: 'std::unordered_map<int, std::set<int> >::mapped_type' {aka 'class std::set<int>'} has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:153:14: note: in expansion of macro 'ER'
153 | cp[v].bc[lc].ER(u);
| ^~
paint.cpp:7:12: error: 'class std::unordered_map<int, std::set<int> >' has no member named 'ER'
7 | #define ER ER
| ^~
paint.cpp:155:10: note: in expansion of macro 'ER'
155 | cp[v].bc.ER(lc);
| ^~
paint.cpp:8:12: error: 'std::unordered_map<int, std::set<int> >::mapped_type' {aka 'class std::set<int>'} has no member named 'IN'
8 | #define IN IN
| ^~
paint.cpp:156:13: note: in expansion of macro 'IN'
156 | cp[v].bc[c].IN(u);
| ^~