Submission #1127326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127326		Ludissey	Love Polygon (BOI18_polygon)	C++20	Compilation error	0 ms	0 KiB

polygon

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<int> a;
vector<int> req;
vector<int> deg;
int n; 

vector<int> neigh;
vector<vector<int>> neigh2;
vector<vector<int>> neigh3;
vector<int> visited;
vector<int> visited2;
queue<int> leefs;
int rst=0;

vector<vector<int>> compo;
vector<int> compoINDEX;
vector<int> topo;

void dfs(int x){
    visited[x]=1;
    if(!visited[neigh[x]]) dfs(neigh[x]);
    topo.push_back(x);
}

void dfs2(int x){
    if(visited[x]==2) return;
    visited[x]=2;
    compo.back().push_back(x);
    compoINDEX[x]=sz(compo)-1;
    for (auto u : neigh2[x])
    {
        dfs2(u);
    }
}


void dfs3(int x){
    rst++;
    visited2[x]=true;
    bool b=false;
    for (auto u : neigh3[x])
    {
        if(visited2[u]||u==x) {
            continue;
        }
        visited2[u]=true;
        deg[neigh3[u]]--;
        if(deg[neigh3[u]]==0&&neigh3[x]!=neigh3[u]) leefs.push(neigh3[u]);
        break;
    }
    return;    
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    neigh.resize(n);
    neigh2.resize(n);
    deg.resize(n);
    compoINDEX.resize(n);
    visited.resize(n);
    map<string,int> mp;
    map<string,int> mp2;
    int t=0;
    for (int i = 0; i < n; i++)
    {
        string sa; string b; cin >> sa >> b;
        if(mp.find(sa)==mp.end()){
             //cerr << sa << " " << t<< "\n";
             mp[sa]=mp2[sa]=t++;
        }
        if(mp.find(b)==mp.end()) {
            //cerr << b << " " << t <<"\n";
            mp[b]=mp2[b]=t++;

        }
        neigh[mp[sa]]=mp[b];
        neigh2[mp[b]].push_back(mp[sa]);
        while(mp[sa]!=mp2[sa]||mp2[b]!=mp2[b]) {

        }
    }
    
    for (int i = 0; i < n; i++)  
    {
        if(visited[i]==0) dfs(i);
    }
    for (int i = n-1; i >= 0; i--)  
    {
        if(visited[topo[i]]==2) continue;
        compo.push_back({});
        dfs2(topo[i]);
    }
    neigh3.resize(sz(compo));
    visited2.resize(sz(compo));
    for (int i = 0; i < n; i++)  
    {
        neigh3[compoINDEX[i]]=compoINDEX[neigh[i]];
    }
    for (int i = 0; i < sz(compo); i++)  
    {
        if(sz(compo[i])%2==0){
            visited2[i]=1;
            if(sz(compo[i])>2) rst+=sz(compo[i])/2;
        }else{
            rst+=(sz(compo[i])-1)/2;
        }
        deg[neigh3[i]]++;
    }
    for (int i = 0; i < sz(compo); i++)  
    {
        if(deg[i]==0) leefs.push(i);
    }
    while(!leefs.empty())
    {
        int u=leefs.front(); leefs.pop();
        if(visited2[u]) continue;
        dfs3(u);
    }
    for (int i = 0; i < sz(compo); i++)  
    {
        if(!visited2[i]) rst++;
    }
    if(n%2) cout << -1 << "\n";
    else cout << rst << "\n";

    return 0;
}

Compilation message (stderr)

polygon.cpp: In function 'void dfs3(long long int)':
polygon.cpp:51:12: error: no match for 'operator[]' (operand types are 'std::vector<long long int>' and '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'})
   51 |         deg[neigh3[u]]--;
      |            ^
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from polygon.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:1043:7: note: candidate: 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::reference = long long int&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
 1043 |       operator[](size_type __n) _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1043:28: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'} to 'std::vector<long long int>::size_type' {aka 'long unsigned int'}
 1043 |       operator[](size_type __n) _GLIBCXX_NOEXCEPT
      |                  ~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:1061:7: note: candidate: 'std::vector<_Tp, _Alloc>::const_reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) const [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::const_reference = const long long int&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
 1061 |       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1061:28: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'} to 'std::vector<long long int>::size_type' {aka 'long unsigned int'}
 1061 |       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
      |                  ~~~~~~~~~~^~~
polygon.cpp:52:15: error: no match for 'operator[]' (operand types are 'std::vector<long long int>' and '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'})
   52 |         if(deg[neigh3[u]]==0&&neigh3[x]!=neigh3[u]) leefs.push(neigh3[u]);
      |               ^
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from polygon.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:1043:7: note: candidate: 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::reference = long long int&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
 1043 |       operator[](size_type __n) _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1043:28: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'} to 'std::vector<long long int>::size_type' {aka 'long unsigned int'}
 1043 |       operator[](size_type __n) _GLIBCXX_NOEXCEPT
      |                  ~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:1061:7: note: candidate: 'std::vector<_Tp, _Alloc>::const_reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) const [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::const_reference = const long long int&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
 1061 |       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1061:28: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'} to 'std::vector<long long int>::size_type' {aka 'long unsigned int'}
 1061 |       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
      |                  ~~~~~~~~~~^~~
polygon.cpp:52:63: error: no matching function for call to 'std::queue<long long int>::push(__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type&)'
   52 |         if(deg[neigh3[u]]==0&&neigh3[x]!=neigh3[u]) leefs.push(neigh3[u]);
      |                                                     ~~~~~~~~~~^~~~~~~~~~~
In file included from /usr/include/c++/11/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:86,
                 from polygon.cpp:1:
/usr/include/c++/11/bits/stl_queue.h:265:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(const value_type&) [with _Tp = long long int; _Sequence = std::deque<long long int, std::allocator<long long int> >; std::queue<_Tp, _Sequence>::value_type = long long int]'
  265 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/11/bits/stl_queue.h:265:30: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'} to 'const value_type&' {aka 'const long long int&'}
  265 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_queue.h:270:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(std::queue<_Tp, _Sequence>::value_type&&) [with _Tp = long long int; _Sequence = std::deque<long long int, std::allocator<long long int> >; std::queue<_Tp, _Sequence>::value_type = long long int]'
  270 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/11/bits/stl_queue.h:270:25: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'} to 'std::queue<long long int>::value_type&&' {aka 'long long int&&'}
  270 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
polygon.cpp: In function 'int main()':
polygon.cpp:102:50: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'} and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
  102 |         neigh3[compoINDEX[i]]=compoINDEX[neigh[i]];
      |                                                  ^
In file included from /usr/include/c++/11/vector:72,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from polygon.cpp:1:
/usr/include/c++/11/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++/11/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'const std::vector<long long int>&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from polygon.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_vector.h:709:26: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'std::vector<long long int>&&'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/11/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++/11/bits/stl_vector.h:730:46: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'std::initializer_list<long long int>'
  730 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
polygon.cpp:112:12: error: no match for 'operator[]' (operand types are 'std::vector<long long int>' and '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'})
  112 |         deg[neigh3[i]]++;
      |            ^
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from polygon.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:1043:7: note: candidate: 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::reference = long long int&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
 1043 |       operator[](size_type __n) _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1043:28: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'} to 'std::vector<long long int>::size_type' {aka 'long unsigned int'}
 1043 |       operator[](size_type __n) _GLIBCXX_NOEXCEPT
      |                  ~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:1061:7: note: candidate: 'std::vector<_Tp, _Alloc>::const_reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) const [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::const_reference = const long long int&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
 1061 |       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1061:28: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'} to 'std::vector<long long int>::size_type' {aka 'long unsigned int'}
 1061 |       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
      |                  ~~~~~~~~~~^~~