Submission #788526

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
788526	2023-07-20T10:21:41 Z	alexander707070	Fountain Parks (IOI21_parks)	C++17	Compilation error	0 ms	0 KB

parks

#include<bits/stdc++.h>
#include "parks.h"
#define MAXN 800007
using namespace std;

struct bench{
    int from,to;
    int a,b;
};

int n,curr,benches,br,k,comp[MAXN],ans[MAXN],dsu[MAXN],w[MAXN];
bool li[MAXN];
vector<int> v[MAXN],r[MAXN];
stack<int> st;

vector<bench> sol;
vector<int> A,B,C,D;
vector< pair<int,int> > ors;

unordered_map<long long, int> mp;
map< pair<int,int>, vector<int> > bro;

int op(int x){
    if(x<400000)return x+400000;
    return x-400000;
}

void add(int x,int y,int z){
    for(int i=0;i<bro[{x,y}].size();i++){
        ors.push_back({op(bro[{x,y}][i]),op(z)});
    }
    bro[{x,y}].push_back(z);
}

void dfs(int x){
    li[x]=true;
    for(int i=0;i<v[x].size();i++){
        if(!li[v[x][i]])dfs(v[x][i]);
    }
    st.push(x);
}

void scc(int x){
    comp[x]=k;
    li[x]=true;

    for(int i=0;i<r[x].size();i++){
        if(!li[r[x][i]])scc(r[x][i]);
    }
}

int root(int x){
    if(dsu[x]==x)return x;
    dsu[x]=root(dsu[x]);
    return dsu[x];
}

void mergev(int x,int y){
    dsu[root(x)]=root(y);
}

vector<long long> x,y;

int construct_roads(vector<int> X,vector<int> Y){
    n=int(X.size());
    x=X; y=Y;

    for(int i=0;i<n;i++){
        dsu[i]=i;
        mp[x[i]*300000+y[i]]=i+1;
    }

    br=0;
    for(int i=0;i<n;i++){
        curr=mp[x[i]*300000+y[i]-2];
        if(curr!=0 and root(i)!=root(curr-1)){
            curr--; mergev(i,curr);

            add(x[i]-1,y[i]-1,br);
            add(x[i]+1,y[i]-1,br+1);
            ors.push_back({br,br+1});

            br+=2;
        }
    }

    for(int i=0;i<n;i++){
        curr=mp[(x[i]-2)*300000+y[i]];
        if(curr!=0 and root(i)!=root(curr-1)){
            curr--; mergev(i,curr);

            add(x[i]-1,y[i]-1,br);
            add(x[i]-1,y[i]+1,br+1);
            ors.push_back({br,br+1});
            
            br+=2;
        }
    } 

    if(br!=2*n-2)return 0;

    for(int i=0;i<ors.size();i++){
        v[op(ors[i].first)].push_back(ors[i].second);
        r[ors[i].second].push_back(op(ors[i].first));

        v[op(ors[i].second)].push_back(ors[i].first);
        r[ors[i].first].push_back(op(ors[i].second));
    }

    for(int i=0;i<800000;i++){
        if(!li[i])dfs(i);
    }
    for(int i=0;i<800000;i++)li[i]=false;
    while(!st.empty()){
        if(!li[st.top()]){
            k++; scc(st.top());
        }
        st.pop();
    }

    for(int i=0;i<br;i++){
        if(comp[i]==comp[op(i)])return 0;
        if(comp[i]<comp[op(i)])ans[i]=0;
        else ans[i]=1;
    }

    for(int i=0;i<n;i++)dsu[i]=i;

    br=0;
    for(int i=0;i<n;i++){
        curr=mp[x[i]*300000+y[i]-2];
        if(curr!=0 and root(i)!=root(curr-1)){
            curr--; mergev(i,curr);

            if(ans[br]==0 and ans[br+1]==0)return -1;
            if(ans[br]==1){
                sol.push_back({curr,i,x[i]-1,y[i]-1});
            }else{
                sol.push_back({curr,i,x[i]+1,y[i]-1});
            }

            br+=2;
        }
    }

    for(int i=0;i<n;i++){
        curr=mp[(x[i]-2)*300000+y[i]];
        if(curr!=0 and root(i)!=root(curr-1)){
            curr--; mergev(i,curr);
        
            if(ans[br]==0 and ans[br+1]==0)return -1;
            if(ans[br]==1){
                sol.push_back({curr,i,x[i]-1,y[i]-1});
            }else{
                sol.push_back({curr,i,x[i]-1,y[i]+1});
            }
            
            br+=2;
        }
    }
    
    for(int i=0;i<sol.size();i++){
        A.push_back(sol[i].from);
        B.push_back(sol[i].to);
        C.push_back(sol[i].a);
        D.push_back(sol[i].b);
    }

    build(A,B,C,D);
    return 1;
}

/*
int main(){
    cout<<construct_roads({4, 4, 6, 4, 2}, {4, 6, 4, 2, 4});
}
*/

Compilation message

parks.cpp: In function 'void add(int, int, int)':
parks.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<bro[{x,y}].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~~
parks.cpp: In function 'void dfs(int)':
parks.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
parks.cpp: In function 'void scc(int)':
parks.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<r[x].size();i++){
      |                 ~^~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:66:7: error: no match for 'operator=' (operand types are 'std::vector<long long int>' and 'std::vector<int>')
   66 |     x=X; y=Y;
      |       ^
In file included from /usr/include/c++/10/vector:72,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from parks.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::vector<long long int>&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from parks.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<long long int>&&'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  730 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::initializer_list<long long int>'
  730 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
parks.cpp:66:12: error: no match for 'operator=' (operand types are 'std::vector<long long int>' and 'std::vector<int>')
   66 |     x=X; y=Y;
      |            ^
In file included from /usr/include/c++/10/vector:72,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from parks.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::vector<long long int>&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from parks.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<long long int>&&'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  730 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::initializer_list<long long int>'
  730 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
parks.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<ors.size();i++){
      |                 ~^~~~~~~~~~~
parks.cpp:137:43: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  137 |                 sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:137:50: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  137 |                 sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:139:43: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) + 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  139 |                 sol.push_back({curr,i,x[i]+1,y[i]-1});
parks.cpp:139:50: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  139 |                 sol.push_back({curr,i,x[i]+1,y[i]-1});
parks.cpp:153:43: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  153 |                 sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:153:50: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  153 |                 sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:155:43: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  155 |                 sol.push_back({curr,i,x[i]-1,y[i]+1});
parks.cpp:155:50: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) + 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  155 |                 sol.push_back({curr,i,x[i]-1,y[i]+1});
parks.cpp:162:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |     for(int i=0;i<sol.size();i++){
      |                 ~^~~~~~~~~~~