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>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
typedef long long ll;
using namespace std;
int R,S,N,Q;
vector<vector<int> > num, col;
struct DSU{
int grp[200011];
int col[200011];
vector<int> comp[200011];
vector<int> adj[200011];
void init(){
forf(i,1,N){
grp[i] = i;
comp[i].push_back(i);
}
}
int f(int x){
if(grp[x] == x) return x;
return grp[x] = f(grp[x]);
}
void u(int x, int y){
x = f(x); y=f(y);
if(adj[x].size() > adj[y].size()) swap(x,y);
for(int &i : adj[x]) adj[y].push_back(i);
adj[x].clear();
grp[x] = y;
}
void merg(int x){
vector<int> q;
for(int i : adj[x]){
if(f(i) == f(x)) continue;
if(col[f(i)] == col[f(x)]) q.push_back(i);
}
for(int i : q){
if(f(i)!=f(x)) u(x,i);
}
}
} dsu;
void setdsu(){
forf(i,1,R){
forf(j,1,S){
dsu.col[num[i][j]] = col[i][j];
}
}
forf(i,1,R-1){
forf(j,1,S){
dsu.adj[num[i][j]].push_back(num[i+1][j]);
dsu.adj[num[i+1][j]].push_back(num[i][j]);
}
}
forf(i,1,R){
forf(j,1,S-1){
dsu.adj[num[i][j+1]].push_back(num[i][j]);
dsu.adj[num[i][j]].push_back(num[i][j+1]);
}
}
}
int main(){
scanf("%d %d" , &R,&S);
N=R*S;
num.resize(R+2); col.resize(R+2);
forf(i,0,R+1){num[i] = vector<int>(S+2,-1); col[i] = vector<int>(S+2,-1);}
dsu.init();
forf(i,1,R){
forf(j,1,S){
scanf("%d" , &col[i][j]);
num[i][j] = S*(i-1)+j;
}
}
setdsu();
forf(i,1,R){
forf(j,1,S){
dsu.merg(num[i][j]);
}
}
scanf("%d" , &Q);
while(Q--){
int x,y,c;
scanf("%d %d %d" , &x,&y,&c);
dsu.col[dsu.f(num[x][y])]=c;
dsu.merg(dsu.f(num[x][y]));
}
forf(i,1,R) {
forf(j, 1, S) printf("%d " , dsu.col[dsu.f(num[i][j])]);
printf("\n");
}
}
Compilation message (stderr)
paint.cpp: In function 'int main()':
paint.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d %d" , &R,&S);
| ~~~~~^~~~~~~~~~~~~~~~~
paint.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d" , &col[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d" , &Q);
| ~~~~~^~~~~~~~~~~
paint.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d %d %d" , &x,&y,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |