#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
const int BUCK = 1;
const int DEB = 0;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
struct node_t{
int color;
bool initialized;
vector<int> cells;
unordered_map<int,unordered_set<int> > neighbors;
void merge(const node_t &other){
for(auto it:other.cells){
this->cells.push_back(it);
}
for(auto it:other.neighbors){
for(auto it2:it.second){
this->neighbors[it.first].insert(it2);
}
}
}
int size(){
return (int)cells.size();
}
};
class DSU{
int n,m;
vector<int> father;
vector<node_t> stuff;
vector<int> big_roots;
int coord_to_pos(int x,int y){
return (x - 1) * m + y;
}
pair<int,int> pos_to_coord(int pos){
return {(pos - 1) / m + 1,(pos - 1) % m + 1};
}
int find_root(int nod){
if(father[nod] == 0){
return nod;
}
return father[nod] = find_root(father[nod]);
}
bool unite(int x,int y){
x = find_root(x);
y = find_root(y);
if(x == y){
return false;
}
if(stuff[x].size() > stuff[y].size()){
swap(x,y);
}
father[x] = y;
stuff[y].merge(stuff[x]);
return true;
}
public:
DSU(int n,int m){
this->n = n;
this->m = m;
father = vector<int>(n * m + 1,0);
stuff = vector<node_t>(n * m + 1);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
stuff[coord_to_pos(i,j)].cells = {coord_to_pos(i,j)};
scanf("%d",&stuff[coord_to_pos(i,j)].color);
}
}
}
void update_color(int x,int y,int c){
int root = find_root(coord_to_pos(x,y));
if(DEB){
printf("root %d\n",root);
}
int initial_size = stuff[root].size();
vector<int> to_unite;
if(stuff[root].size() >= BUCK && stuff[root].initialized == true){
for(auto it:stuff[root].neighbors[c]){
int neighbor_root = find_root(it);
if(DEB){
printf("deb %d %d %d\n",root,neighbor_root,stuff[neighbor_root].color);
}
if(stuff[neighbor_root].color == c){
to_unite.push_back(neighbor_root);
}
}
stuff[root].neighbors[c].clear();
}
else{
for(auto it:stuff[root].cells){
int x = pos_to_coord(it).first;
int y = pos_to_coord(it).second;
for(int k = 0;k < 4;k++){
int xx = x + dx[k];
int yy = y + dy[k];
if(1 <= xx && xx <= n && 1 <= yy && yy <= m){
int neighbor_root = find_root(coord_to_pos(xx,yy));
if(DEB){
printf("deb %d %d %d\n",root,neighbor_root,stuff[neighbor_root].color);
}
if(stuff[neighbor_root].color == c && stuff[neighbor_root].initialized == true){
to_unite.push_back(neighbor_root);
}
}
}
}
}
for(auto it:to_unite){
if(DEB){
printf("unite %d %d\n",root,it);
}
unite(root,it);
}
root = find_root(coord_to_pos(x,y));
stuff[root].color = c;
if(initial_size < BUCK || stuff[root].initialized == false){
stuff[root].initialized = true;
if(stuff[root].size() >= BUCK){
big_roots.push_back(root);
}
for(auto it:stuff[root].cells){
int x = pos_to_coord(it).first;
int y = pos_to_coord(it).second;
for(int k = 0;k < 4;k++){
int xx = x + dx[k];
int yy = y + dy[k];
if(1 <= xx && xx <= n && 1 <= yy && yy <= m){
int neighbor_root = find_root(coord_to_pos(xx,yy));
if(root != neighbor_root){
if(stuff[neighbor_root].size() >= BUCK && stuff[neighbor_root].initialized == true){
stuff[neighbor_root].neighbors[c].insert(root);
}
if(stuff[root].size() >= BUCK){
stuff[root].neighbors[stuff[neighbor_root].color].insert(neighbor_root);
}
}
}
}
}
}
else{
for(auto &it:big_roots){
it = find_root(it);
if(it != root && stuff[root].neighbors[stuff[it].color].count(it)){
stuff[it].neighbors[c].insert(root);
}
}
}
if(DEB){
printf("end root %d\n\n",root);
}
}
int get_color(int x,int y){
return stuff[find_root(coord_to_pos(x,y))].color;
}
void print(){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
// printf("%d ",find_root(coord_to_pos(i,j)));
printf("%d ",get_color(i,j));
}
printf("\n");
}
}
};
int main(){
int n,m;
scanf("%d %d",&n,&m);
DSU solver(n,m);
if(DEB){
solver.print();
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
solver.update_color(i,j,solver.get_color(i,j));
}
}
int q;
scanf("%d",&q);
while(q--){
int x,y,c;
scanf("%d %d %d",&x,&y,&c);
solver.update_color(x,y,c);
if(DEB){
solver.print();
}
}
solver.print();
return 0;
}
Compilation message
paint.cpp: In function 'int main()':
paint.cpp:198:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
198 | scanf("%d %d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
paint.cpp:213:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
213 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
paint.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
217 | scanf("%d %d %d",&x,&y,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
paint.cpp: In constructor 'DSU::DSU(int, int)':
paint.cpp:90:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
90 | scanf("%d",&stuff[coord_to_pos(i,j)].color);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
876 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
1004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3071 ms |
24308 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3067 ms |
62332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3040 ms |
41332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
