| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 847323 |
2023-09-09T13:33:41 Z |
BidoTeima |
Paint (COI20_paint) |
C++17 |
|
0 ms |
0 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, 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 1;
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;
}
Compilation message
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from paint.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = int; _Iterator2 = int]':
/usr/include/c++/10/bits/stl_algo.h:4905:14: required from '_OutputIterator std::__merge(_InputIterator1, _InputIterator1, _InputIterator2, _InputIterator2, _OutputIterator, _Compare) [with _InputIterator1 = int; _InputIterator2 = int; _OutputIterator = int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:4963:37: required from '_OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter) [with _IIter1 = int; _IIter2 = int; _OIter = int]'
paint.cpp:26:43: required from here
/usr/include/c++/10/bits/predefined_ops.h:43:16: error: invalid type argument of unary '*' (have 'int')
43 | { return *__it1 < *__it2; }
| ^~~~~~
/usr/include/c++/10/bits/predefined_ops.h:43:25: error: invalid type argument of unary '*' (have 'int')
43 | { return *__it1 < *__it2; }
| ^~~~~~
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from paint.cpp:1:
/usr/include/c++/10/bits/stl_algo.h: In instantiation of '_OutputIterator std::__merge(_InputIterator1, _InputIterator1, _InputIterator2, _InputIterator2, _OutputIterator, _Compare) [with _InputIterator1 = int; _InputIterator2 = int; _OutputIterator = int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]':
/usr/include/c++/10/bits/stl_algo.h:4963:37: required from '_OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter) [with _IIter1 = int; _IIter2 = int; _OIter = int]'
paint.cpp:26:43: required from here
/usr/include/c++/10/bits/stl_algo.h:4907:8: error: invalid type argument of unary '*' (have 'int')
4907 | *__result = *__first2;
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:4907:20: error: invalid type argument of unary '*' (have 'int')
4907 | *__result = *__first2;
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:4912:8: error: invalid type argument of unary '*' (have 'int')
4912 | *__result = *__first1;
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:4912:20: error: invalid type argument of unary '*' (have 'int')
4912 | *__result = *__first1;
| ^~~~~~~~~
