This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY 100000000000005
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 200005
#define fi first
#define se second
int r,s;
int dizi[lim],vis[lim];// x-y
int old_par[lim];// x-y
int color[4*lim];
int xd[4]={0,0,-1,1},yd[4]={1,-1,0,0};
int par[lim],siz[lim];
set<int> st[lim];
set<int> ekle;
int index(int x,int y){
return (x-1)*s+y;
}
inline bool cont(int x,int y){
if(x<1 || y<1 || x>r || y>s)return 0;
return 1;
}
inline void dfs(int x,int y,int renk,int now){
if(!cont(x,y))return;
if(dizi[index(x,y)]!=now)return ;
if(vis[index(x,y)])return ;
vis[index(x,y)]=1;
old_par[index(x,y)]=renk;
for(int i=0;i<4;i++){
dfs(x+xd[i],y+yd[i],renk,now);
}
}
inline void dfs2(int x,int y){
if(!cont(x,y))return;
if(vis[index(x,y)])return ;
vis[index(x,y)]=1;
for(int i=0;i<4;i++){
int nx=x+xd[i];
int ny=y+yd[i];
if(cont(nx,ny) && dizi[index(x,y)]!=dizi[index(nx,ny)]){
st[old_par[index(nx,ny)]].insert(old_par[index(x,y)]);
st[old_par[index(x,y)]].insert(old_par[index(nx,ny)]);
}
dfs2(nx,ny);
}
}
inline int find(int node){
if(par[node]==node)return node;
return par[node]=find(par[node]);
}
inline void unite(int node1,int node2){
if(siz[node1]<siz[node2])swap(node1,node2);
//cout<<node1<<" "<<node2<<endl;
par[node2]=par[node1];
siz[node1]+=siz[node2];
for(auto x:st[node2]){
if(find(x)!=node1)st[node1].insert(x);
}
//st[node1].erase(node2);
/*cout<<endl;
for(auto x:st[node1])cout<<x<<" ";
cout<<"b"<<endl;*/
}
int32_t main(){
//faster
cin>>r>>s;
for(int i=1;i<=r;i++){
for(int j=1;j<=s;j++){
cin>>dizi[index(i,j)];
}
}
int cur=1;
for(int i=1;i<=r;i++){
for(int j=1;j<=s;j++){
if(vis[index(i,j)]==0){
dfs(i,j,cur,dizi[index(i,j)]);
color[cur]=dizi[index(i,j)];
cur++; // node olarak tanımlama
}
}
}
memset(vis,0,sizeof(vis));
/*cout<<endl;
for(int i=1;i<=r;i++){
for(int j=1;j<=s;j++){
cout<<old_par[i][j]<<" ";
}
cout<<endl;
}
*/
dfs2(1,1);
/*
for(int i=1;i<cur;i++){
cout<<i<<" "<<st[i].size()<<endl;
for(auto x:st[i])cout<<x<<" ";
cout<<endl<<endl;
}
*/
////////////////////////////////////////////////////////////////////
for(int i=1;i<cur;i++){
siz[i]=1;
par[i]=i;
}
int q;cin>>q;
while(q--){
int a,b,val;cin>>a>>b>>val;
int nod=find(old_par[index(a,b)]);
//cout<<nod<<endl;
for(auto komsu:st[nod]){
//cout<<find(komsu)<<" "<<komsu<<" "<<color[find(komsu)]<<endl;
if(find(komsu)==nod)continue;
if(color[find(komsu)]==val){
unite(nod,find(komsu));
}
}
/*for(auto x:ekle)st[nod].insert(x);
ekle.clear();*/
color[nod]=val;
}
/*
for(int i=1;i<cur;i++){
cout<<par[i]<<" ";
}*/
for(int i=1;i<=r;i++){
for(int j=1;j<=s;j++){
cout<<color[find(old_par[index(i,j)])]<<" ";
}
cout<<'\n';
}
return 0;
}
# | 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... |