Submission #847323

# Submission time Handle Problem Language Result Execution time Memory
847323 2023-09-09T13:33:41 Z BidoTeima Paint (COI20_paint) C++17
Compilation error
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;
      |                    ^~~~~~~~~