Submission #942215

#TimeUsernameProblemLanguageResultExecution timeMemory
942215elotelo966Paint (COI20_paint)C++17
0 / 100
45 ms37356 KiB
#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 1005 #define fi first #define se second int r,s; int dizi[lim][lim],vis[lim][lim]; int old_par[lim][lim]; 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; 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[x][y]!=now)return ; if(vis[x][y])return ; vis[x][y]=1; old_par[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[x][y])return ; vis[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[x][y]!=dizi[nx][ny]){ st[old_par[nx][ny]].insert(old_par[x][y]); st[old_par[x][y]].insert(old_par[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)ekle.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[i][j]; } } int cur=1; for(int i=1;i<=r;i++){ for(int j=1;j<=s;j++){ if(vis[i][j]==0){ dfs(i,j,cur,dizi[i][j]); color[cur]=dizi[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[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[i][j])]<<" "; } cout<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...