Submission #735471

#	Time	Username	Problem	Language	Result	Execution time	Memory
735471		keisuke6	Swapping Cities (APIO20_swap)	C++14	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

swap

#include "swap.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N,M;
vector<int> U,V,W,W_;
vector<tuple<int,int,int>> S = {};
struct Unionfind{
  vector<int> par, siz;
  //初期化
  Unionfind(int n) : par(n,-1) , siz(n,1) {}
  int root(int x) {
    if(par[x] == -1) return x;
    else return par[x] = root(par[x]);
  }
  bool issame(int x,int y) {
    return root(x) == root(y);
  }
  bool unite(int x, int y){
    x = root(x); y = root(y);
    if(x ==  y) return false;
    if(siz[x] < siz[y]) swap(x,y);
    par[y] =  x;
    siz[x] += siz[y];
    return  true;
  }
  int size(int x) {
    return siz[root(x)];
  }
};
void init(int NN, int MM,
          std::vector<int> UU, std::vector<int> VV, std::vector<int> WW) {
            N = NN;
            M = MM;
            U = UU;
            V = VV;
            W = WW;
            W_ = W;
            for(int i=0;i<M;i++){
              S.push_back({W[i],U[i],V[i]});
            }
            sort(S.begin(),S.end());
}
 
int getMinimumFuelCapacity(int X, int Y) {
  vector<int> E = {};
  vector<vector<int>> G(N);
  bool cone = false;
  Unionfind uf(N);
  for(int i=0;i<M;i++){
    int w,u,v;
    tie(w,u,v) = S[i];
    if(cone && uf.issame(u,v) && uf.issame(u,X)) return w;
    uf.unite(u,v);
    G[u].push_back(v);
    G[v].push_back(u);
    if(uf.issame(X,Y) && !cone){
      cone = true;
      vector<int> dist(N,1e9);
      dist[X] = 0;
      queue<int> q;
      q.push(X);
      while(!q.empty()){
        int pos = q.front();
        q.pop();
        for(int x:G[pos]){
          if(dist[x] != 1e9) continue;
          dist[x] = dist[pos] + 1;
          q.push(x);
          continue;
        }
      }
      int now = Y;
      while(now){
        if(now != Y) E.push_back(now);
        for(int x:G[now]){
          if(dist[x]+1 == dist[now]){
            now = x;
            continue;
          }
        }
      }
      for(int x:E){
        if(G[x].size() >= 3) return w;
      }
    }
    if(cone){
      if(G[u].size() >= 3 || G[v].size() >= 3) return w;
    }
  }
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:41:43: error: no matching function for call to 'std::vector<std::tuple<int, int, int> >::push_back(<brace-enclosed initializer list>)'
   41 |               S.push_back({W[i],U[i],V[i]});
      |                                           ^
In file included from /usr/include/c++/10/vector:67,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >; std::vector<_Tp, _Alloc>::value_type = std::tuple<int, int, int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::tuple<int, int, int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >; std::vector<_Tp, _Alloc>::value_type = std::tuple<int, int, int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::tuple<int, int, int> >::value_type&&' {aka 'std::tuple<int, int, int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
swap.cpp:43:13: error: 'sort' was not declared in this scope; did you mean 'qsort'?
   43 |             sort(S.begin(),S.end());
      |             ^~~~
      |             qsort
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:53:5: error: 'tie' was not declared in this scope
   53 |     tie(w,u,v) = S[i];
      |     ^~~
swap.cpp:5:1: note: 'std::tie' is defined in header '<tuple>'; did you forget to '#include <tuple>'?
    4 | #include <queue>
  +++ |+#include <tuple>
    5 | using namespace std;
In file included from /usr/include/c++/10/vector:67,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >]':
/usr/include/c++/10/bits/stl_vector.h:487:7:   required from here
/usr/include/c++/10/bits/stl_vector.h:336:35: error: invalid use of incomplete type 'class std::tuple<int, int, int>'
  336 |         _M_impl._M_end_of_storage - _M_impl._M_start);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: declaration of 'class std::tuple<int, int, int>'
 2631 |     class tuple;
      |           ^~~~~
In file included from /usr/include/c++/10/vector:67,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_vector.h: In instantiation of 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >; std::vector<_Tp, _Alloc>::reference = std::tuple<int, int, int>&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]':
swap.cpp:53:21:   required from here
/usr/include/c++/10/bits/stl_vector.h:1046:34: error: invalid use of incomplete type 'class std::tuple<int, int, int>'
 1046 |  return *(this->_M_impl._M_start + __n);
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: declaration of 'class std::tuple<int, int, int>'
 2631 |     class tuple;
      |           ^~~~~
/usr/include/c++/10/type_traits: In instantiation of 'struct std::is_destructible<std::tuple<int, int, int> >':
/usr/include/c++/10/bits/stl_construct.h:177:51:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<int, int, int>*]'
/usr/include/c++/10/bits/alloc_traits.h:738:15:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::tuple<int, int, int>*; _Tp = std::tuple<int, int, int>]'
/usr/include/c++/10/bits/stl_vector.h:680:15:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >]'
swap.cpp:8:33:   required from here
/usr/include/c++/10/type_traits:844:52: error: static assertion failed: template argument must be a complete class or an unbounded array
  844 |       static_assert(std::__is_complete_or_unbounded(__type_identity<_Tp>{}),
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/vector:65,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_construct.h: In instantiation of 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<int, int, int>*]':
/usr/include/c++/10/bits/alloc_traits.h:738:15:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::tuple<int, int, int>*; _Tp = std::tuple<int, int, int>]'
/usr/include/c++/10/bits/stl_vector.h:680:15:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >]'
swap.cpp:8:33:   required from here
/usr/include/c++/10/bits/stl_construct.h:177:51: error: static assertion failed: value type is destructible
  177 |       static_assert(is_destructible<_Value_type>::value,
      |                                                   ^~~~~
/usr/include/c++/10/bits/stl_construct.h:184:25: error: invalid use of incomplete type 'std::iterator_traits<std::tuple<int, int, int>*>::value_type' {aka 'class std::tuple<int, int, int>'}
  184 |       std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
      |                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: declaration of 'std::iterator_traits<std::tuple<int, int, int>*>::value_type' {aka 'class std::tuple<int, int, int>'}
 2631 |     class tuple;
      |           ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
                 from /usr/include/c++/10/bits/allocator.h:46,
                 from /usr/include/c++/10/vector:64,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::deallocate(_Tp*, __gnu_cxx::new_allocator<_Tp>::size_type) [with _Tp = std::tuple<int, int, int>; __gnu_cxx::new_allocator<_Tp>::size_type = long unsigned int]':
/usr/include/c++/10/bits/alloc_traits.h:492:23:   required from 'static void std::allocator_traits<std::allocator<_Tp1> >::deallocate(std::allocator_traits<std::allocator<_Tp1> >::allocator_type&, std::allocator_traits<std::allocator<_Tp1> >::pointer, std::allocator_traits<std::allocator<_Tp1> >::size_type) [with _Tp = std::tuple<int, int, int>; std::allocator_traits<std::allocator<_Tp1> >::allocator_type = std::allocator<std::tuple<int, int, int> >; std::allocator_traits<std::allocator<_Tp1> >::pointer = std::tuple<int, int, int>*; std::allocator_traits<std::allocator<_Tp1> >::size_type = long unsigned int]'
/usr/include/c++/10/bits/stl_vector.h:354:19:   required from 'void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(std::_Vector_base<_Tp, _Alloc>::pointer, std::size_t) [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >; std::_Vector_base<_Tp, _Alloc>::pointer = std::tuple<int, int, int>*; std::size_t = long unsigned int]'
/usr/include/c++/10/bits/stl_vector.h:335:2:   required from 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int> >]'
/usr/include/c++/10/bits/stl_vector.h:487:7:   required from here
/usr/include/c++/10/ext/new_allocator.h:135:14: error: invalid application of 'sizeof' to incomplete type 'std::tuple<int, int, int>'
  135 |      , __t * sizeof(_Tp)
      |              ^~~~~~~~~~~
swap.cpp:47:20: warning: control reaches end of non-void function [-Wreturn-type]
   47 |   vector<int> E = {};
      |                    ^