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>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int maxn = -1;
const int inf = 1e18+10;
vector<vector<int>> a, dscol;
vector<vector<pair<int,int>>> ds;
vector<vector<vector<pair<int,int>>>> dsedg;
vector<pair<int,int>> adj = {{0,1},{0,-1},{1,0},{-1,0}};
pair<int,int> find(pair<int,int> u) {
if(u == ds[u.fr][u.sc]) return u;
return ds[u.fr][u.sc] = find(ds[u.fr][u.sc]);
}
void join(pair<int,int> u, pair<int,int> v) {
u = find(u);
v = find(v);
if(u == v) return;
if(dsedg[u.fr][u.sc].size() < dsedg[v.fr][v.sc].size()) swap(u,v);
ds[v.fr][v.sc] = u;
for(auto x : dsedg[v.fr][v.sc]) {
dsedg[u.fr][u.sc].pb(x);
}
}
void upd(pair<int,int> u) {
u = find(u);
dscol[u.fr][u.sc]^= 1;
vector<pair<int,int>> edgs = dsedg[u.fr][u.sc];
dsedg[u.fr][u.sc].clear();
for(auto v : edgs) {
join(u,v);
}
}
int32_t main() {
// #ifndef ONLINE_JUDGE
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
// #endif
int n,m;
cin >> n >> m;
ds.resize(n+1,vector<pair<int,int>>(m+1));
a.resize(n+1,vector<int>(m+1));
dscol.resize(n+1,vector<int>(m+1));
dsedg.resize(n+1,vector<vector<pair<int,int>>>(m+1));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
dscol[i][j] = a[i][j];
ds[i][j] = mp(i,j);
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
for(auto X : adj) {
int i1 = i+X.fr;
int j1 = j+X.sc;
if(i1 >= 1 && i1 <= n && j1 >= 1 && j1 <= m) {
if(a[i][j] != a[i1][j1]) dsedg[i][j].pb(mp(i1,j1));
}
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
for(auto X : adj) {
int i1 = i+X.fr;
int j1 = j+X.sc;
if(i1 >= 1 && i1 <= n && j1 >= 1 && j1 <= m) {
if(a[i][j] == a[i1][j1]) join(mp(i,j),mp(i1,j1));
}
}
}
}
int q;cin >> q;
while(q--) {
int i,j,c;
cin >> i >> j >> c;
pair<int,int> u = mp(i,j);
u = find(u);
if(c == dscol[u.fr][u.sc]) continue;
upd(u);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
pair<int,int> u = mp(i,j);
u = find(u);
cout << dscol[u.fr][u.sc] << " ";
}
cout << endl;
}
}
# | 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... |