| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 847322 | BidoTeima | Paint (COI20_paint) | C++17 | 0 ms | 0 KiB |
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;
typedef long long ll;
int n,m;
vector<vector<pair<int,int>>>par;
vector<vector<vector<pair<int,int>>>>adj;
vector<vector<int>>color;
pair<int, int> find_set(int a, int b){
if(par[a][b] == make_pair(a, b))
return make_pair(a, b);
return par[a][b] = find_set(par[a][b].first, par[a][b].second);
}
bool merge(int a, int b, int x, int y, bool cond){
a = find_set(a, b).first, b = find_set(a,b).second;
x = find_set(x, y).first, y = find_set(x, y).second;
if(a == x && b == y){
return 0;
}
if(color[a][b] != color[x][y])
return 0;
if(adj[a][b].size() == adj[x][y].size() ? rand() % 2 : adj[a][b].size() < adj[x][y].size())
swap(a, x), swap(b, y);
par[x][y] = make_pair(a, b);
if(cond)return;
for(pair<int,int>&pa:adj[a][b]){
merge(a, b, pa.first, pa.second, 1);
}
for(pair<int,int>& pa : adj[x][y]){
if(!merge(a, b, pa.first, pa.second, 1))
adj[a][b].push_back(make_pair(pa.first, pa.second));
}
return 1;
}
int main()
{
srand(time(0));
cin>>n>>m;
par=vector<vector<pair<int,int>>>(n+1, vector<pair<int,int>>(m+1));
adj=vector<vector<vector<pair<int,int>>>>(n+1,vector<vector<pair<int,int>>>(m+1));
color=vector<vector<int>>(n+1,vector<int>(m+1));
int c[n+1][m+1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
par[i][j] = make_pair(i, j);
cin>>c[i][j];
color[i][j] = c[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i >= 2){
merge(i, j, i - 1, j,1);
}
if(j >= 2){
merge(i, j, i, j - 1,1);
}
if(i + 1 <= n){
merge(i, j, i + 1, j,1);
}
if(j + 1 <= m){
merge(i, j, i, j + 1,1);
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i >= 2 && c[i][j] != c[i - 1][j]){
pair<int,int>p1 = find_set(i, j);
pair<int,int>p2 = find_set(i - 1, j);
adj[p1.first][p1.second].push_back(make_pair(p2.first,p2.second));
adj[p2.first][p2.second].push_back(make_pair(p1.first,p1.second));
}
if(j >= 2 && c[i][j] != c[i][j - 1]){
pair<int,int>p1 = find_set(i, j);
pair<int,int>p2 = find_set(i, j - 1);
adj[p1.first][p1.second].push_back(make_pair(p2.first,p2.second));
adj[p2.first][p2.second].push_back(make_pair(p1.first,p1.second));
}
if(i + 1 <= n && c[i][j] != c[i + 1][j]){
pair<int,int>p1 = find_set(i, j);
pair<int,int>p2 = find_set(i + 1, j);
adj[p1.first][p1.second].push_back(make_pair(p2.first,p2.second));
adj[p2.first][p2.second].push_back(make_pair(p1.first,p1.second));
}
if(j + 1 <= m && c[i][j] != c[i][j + 1]){
pair<int,int>p1 = find_set(i, j);
pair<int,int>p2 = find_set(i, j + 1);
adj[p1.first][p1.second].push_back(make_pair(p2.first,p2.second));
adj[p2.first][p2.second].push_back(make_pair(p1.first,p1.second));
}
}
}
int q;
cin>>q;
while(q--){
int i,j,c;
cin>>i>>j>>c;
pair<int,int>p = find_set(i, j);
color[p.first][p.second] = c;
if(i >= 2){
merge(i, j, i - 1, j,0);
}
if(j >= 2){
merge(i, j, i, j - 1,0);
}
if(i + 1 <= n){
merge(i, j, i + 1, j,0);
}
if(j + 1 <= m){
merge(i, j, i, j + 1,0);
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout<<color[find_set(i, j).first][find_set(i, j).second]<<' ';
}
cout<<'\n';
}
return 0;
}