| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 847297 |
2023-09-09T11:51:41 Z |
BidoTeima |
Paint (COI20_paint) |
C++17 |
|
103 ms |
28572 KB |
#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){
tie(a, b) = find_set(a, b);
tie(x, y) = find_set(x, y);
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);
color[x][y] = color[a][b];
for(pair<int,int>& pa : adj[x][y]){
if(!merge(a, b, pa.first, pa.second))
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 && c[i][j] == c[i - 1][j]){
merge(i, j, i - 1, j);
}
if(j >= 2 && c[i][j] == c[i][j - 1]){
merge(i, j, i, j - 1);
}
if(i + 1 <= n && c[i][j] == c[i + 1][j]){
merge(i, j, i + 1, j);
}
if(j + 1 <= m && c[i][j] == c[i][j + 1]){
merge(i, j, i, j + 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);
}
if(j >= 2){
merge(i, j, i, j - 1);
}
if(i + 1 <= n){
merge(i, j, i + 1, j);
}
if(j + 1 <= m){
merge(i, j, i, j + 1);
}
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
8596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
28572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
20532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
