Submission #393742

#TimeUsernameProblemLanguageResultExecution timeMemory
393742sadPaint (COI20_paint)C++14
0 / 100
3066 ms56932 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define fi first #define se second using namespace std; int n,m; const int N=200090; vector<int>a[N],vis[N]; vector<int>v[N],num[N]; int pa[N],co[N]; int get (int x) { if(pa[x]==x)return x; return pa[x]=get(pa[x]); } void merge(int x,int y) { x=get(x); y=get(y); if(x==y)return; if(v[x].size()<v[y].size())swap(x,y); for(auto it:v[y]) { int o=get(it); if(o==x)continue; v[x].pb(o); } v[y].clear(); pa[y]=x; } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=0;i<n+3;i++) { for(int j=0;j<m+3;j++) { num[i].pb(0); } } int r=0; for(int i=1;i<=n;i++) { for(int j=1;j<m+1;j++) { num[i][j]=++r; cin>>co[num[i][j]]; pa[num[i][j]]=num[i][j]; int u=num[i][j],uu=num[i-1][j],uuu=num[i][j-1]; if(i>1) { if(co[u]==co[uu]) { merge(u,num[i-1][j]); } else {v[u].pb(num[i-1][j]); v[num[i-1][j]].pb(u);} } if(j>1) { if(co[u]==co[uuu]) { merge(u,num[i][j-1]); } else {v[u].pb(num[i][j-1]); v[num[i][j-1]].pb(u);} } } } int q;cin>>q; while(q--) { int x,y,c; cin>>x>>y>>c; int u=num[x][y]; if(c==co[u])continue; co[u]=1-co[u]; u=get(u); for(auto it:v[u]) { merge(it,u); } } for(int i=1;i<n+1;i++) { for(int j=1;j<m+1;j++)cout<<co[get(num[i][j])]<<" "; cout<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...