Submission #979732

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
979732	2024-05-11T10:33:09 Z	vjudge1	Swapping Cities (APIO20_swap)	C++17	Compilation error	0 ms	0 KB

swap

#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>


#include "swap.h"

#include <cassert>
#include <cstdio>


using namespace std;
vector<int> g[200005];
pair<int, int> p[200005];
map<pair<int, int>, int> mp, pos;
set<pair<int, int>> st;
int x, y, mx;
bool ok = 0, ok1;
vector<int> A, B, C;
bool us[200005];
vector<int> ff[200005];
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
      x = N;
      y = M;
      if(x - 1 != y) ok = 1;
      for(int i = 0; i < M; i++){
          int a = U[i] + 1, b = V[i] + 1, c = W[i];
          if(a != 1) ok = 1;
          mp[{a, b}] = c;
          mp[{b, a}] = c;

          pos[{a, b}] = i + 1;
          pos[{b, a}] = i + 1; 
          ff[a].push_back(b);
          ff[b].push_back(a);
          st.insert({c, i + 1});
          A.push_back(a);
          B.push_back(b);
          C.push_back(c);
      }
      for(int i = 1; i <= x; i++){
        if(ff[i].size() > 2) ok1 = 1;
      }    
} 
int kol = 0, kol1 = 0;
int dist[200005];
unordered_map<pair<int, int>, int> edge;
void dfs(int k){
  us[k] = 1;
  kol++;
  for(int to : g[k]){
    if(edge[{k, to}] == 0){
      edge[{k, to}]++;
      edge[{to, k}]++;
      kol1++;
    }
    if(us[to]) continue;
    dfs(to);
  }
}
int getMinimumFuelCapacity(int X, int Y) {
  if(!ok1){
    if(x == y) return st.rbegin()->first;
    else return -1;
  }
  if(ok){
      X++;
      Y++;
      int L = 0, R = 1e9 + 1;
      while(L + 1 < R){
        int mid = (L + R) / 2;
        kol = 0;
        for(int i = 0; i <= x; i++){
          g[i].clear();
          us[i] = 0;
        }
        for(int i = 0; i < y; i++){
            if(C[i] <= mid){
              g[A[i]].push_back(B[i]);
              g[B[i]].push_back(A[i]);
            }
        }
        int kk = 0;
        edge.clear();
        kol1 = kol = 0;
        dfs(X);
        for(int i = 1; i <= x; i++)
          if(us[i] == 1 && g[i].size() >= 3) kk++;
        if(!us[Y]){
          L = mid;
          continue;
        }
        if(kol - 1 == kol1 && kk == 0){
          L = mid;
          continue;
        }
        R = mid;
        continue;
      }
      if(R == 1000000001) return -1;
      return R;
  }
  else{
    X++;
    Y++;
    if(x <= 3)
        return -1;
    int mx = 0;
    if(X != 1) mx = mp[{1, X}];
    if(Y != 1) mx = max(mx, mp[{1, Y}]);


    if(X != 1) st.erase({mp[{1, X}], pos[{1, X}]});
    if(Y != 1) st.erase({mp[{1, Y}], pos[{1, Y}]});
    
    pair<int, int> p = *st.begin();
    st.erase(st.begin());
    if(X != 1 && Y != 1){
        st.insert(p);
        if(X != 1) st.insert({mp[{1, X}], pos[{1, X}]});
        if(Y != 1) st.insert({mp[{1, Y}], pos[{1, Y}]});
        return max(mx, p.first);
    }
    else{
        pair<int, int> p1 = *st.begin();
        st.insert(p1);
        st.insert(p);
        if(X != 1) st.insert({mp[{1, X}], pos[{1, X}]});
        if(Y != 1) st.insert({mp[{1, Y}], pos[{1, Y}]});
        return max({mx, p.first, p1.first});
    }
  }
}

Compilation message

swap.cpp:71:36: error: use of deleted function 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<int, int>; _Tp = int; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >]'
   71 | unordered_map<pair<int, int>, int> edge;
      |                                    ^~~~
In file included from /usr/include/c++/10/unordered_map:47,
                 from swap.cpp:5:
/usr/include/c++/10/bits/unordered_map.h:141:7: note: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<int, int>; _Tp = int; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >]' is implicitly deleted because the default definition would be ill-formed:
  141 |       unordered_map() = default;
      |       ^~~~~~~~~~~~~
/usr/include/c++/10/bits/unordered_map.h:141:7: error: use of deleted function 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]'
In file included from /usr/include/c++/10/unordered_map:46,
                 from swap.cpp:5:
/usr/include/c++/10/bits/hashtable.h:451:7: note: 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]' is implicitly deleted because the default definition would be ill-formed:
  451 |       _Hashtable() = default;
      |       ^~~~~~~~~~
/usr/include/c++/10/bits/hashtable.h:451:7: error: use of deleted function 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits>::_Hashtable_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]'
In file included from /usr/include/c++/10/bits/hashtable.h:35,
                 from /usr/include/c++/10/unordered_map:46,
                 from swap.cpp:5:
/usr/include/c++/10/bits/hashtable_policy.h:1791:5: note: 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits>::_Hashtable_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]' is implicitly deleted because the default definition would be ill-formed:
 1791 |     _Hashtable_base() = default;
      |     ^~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1791:5: error: use of deleted function 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_Hash_code_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing]'
/usr/include/c++/10/bits/hashtable_policy.h:1368:7: note: 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_Hash_code_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing]' is implicitly deleted because the default definition would be ill-formed:
 1368 |       _Hash_code_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1368:7: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<_Nm, _Tp, true>::_Hashtable_ebo_helper() [with int _Nm = 1; _Tp = std::hash<std::pair<int, int> >]'
/usr/include/c++/10/bits/hashtable_policy.h:1112:7: note: 'std::__detail::_Hashtable_ebo_helper<_Nm, _Tp, true>::_Hashtable_ebo_helper() [with int _Nm = 1; _Tp = std::hash<std::pair<int, int> >]' is implicitly deleted because the default definition would be ill-formed:
 1112 |       _Hashtable_ebo_helper() = default;
      |       ^~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1112:7: error: use of deleted function 'std::hash<std::pair<int, int> >::hash()'
In file included from /usr/include/c++/10/unordered_map:45,
                 from swap.cpp:5:
/usr/include/c++/10/bits/functional_hash.h:101:12: note: 'std::hash<std::pair<int, int> >::hash()' is implicitly deleted because the default definition would be ill-formed:
  101 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/10/bits/functional_hash.h:101:12: error: no matching function for call to 'std::__hash_enum<std::pair<int, int>, false>::__hash_enum()'
/usr/include/c++/10/bits/functional_hash.h:82:7: note: candidate: 'std::__hash_enum<_Tp, <anonymous> >::__hash_enum(std::__hash_enum<_Tp, <anonymous> >&&) [with _Tp = std::pair<int, int>; bool <anonymous> = false]'
   82 |       __hash_enum(__hash_enum&&);
      |       ^~~~~~~~~~~
/usr/include/c++/10/bits/functional_hash.h:82:7: note:   candidate expects 1 argument, 0 provided
/usr/include/c++/10/bits/functional_hash.h:101:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::pair<int, int>; bool <anonymous> = false]' is private within this context
  101 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/10/bits/functional_hash.h:83:7: note: declared private here
   83 |       ~__hash_enum();
      |       ^
In file included from /usr/include/c++/10/bits/hashtable.h:35,
                 from /usr/include/c++/10/unordered_map:46,
                 from swap.cpp:5:
/usr/include/c++/10/bits/hashtable_policy.h:1112:7: error: use of deleted function 'std::hash<std::pair<int, int> >::~hash()'
 1112 |       _Hashtable_ebo_helper() = default;
      |       ^~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/unordered_map:45,
                 from swap.cpp:5:
/usr/include/c++/10/bits/functional_hash.h:101:12: note: 'std::hash<std::pair<int, int> >::~hash()' is implicitly deleted because the default definition would be ill-formed:
  101 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/10/bits/functional_hash.h:101:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::pair<int, int>; bool <anonymous> = false]' is private within this context
/usr/include/c++/10/bits/functional_hash.h:83:7: note: declared private here
   83 |       ~__hash_enum();
      |       ^
In file included from /usr/include/c++/10/bits/hashtable.h:35,
                 from /usr/include/c++/10/unordered_map:46,
                 from swap.cpp:5:
/usr/include/c++/10/bits/hashtable_policy.h:1368:7: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>::~_Hashtable_ebo_helper()'
 1368 |       _Hash_code_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1109:12: note: 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>::~_Hashtable_ebo_helper()' is implicitly deleted because the default definition would be ill-formed:
 1109 |     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1109:12: error: use of deleted function 'std::hash<std::pair<int, int> >::~hash()'
/usr/include/c++/10/bits/hashtable_policy.h:1791:5: error: use of deleted function 'std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()'
 1791 |     _Hashtable_base() = default;
      |     ^~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1341:12: note: 'std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()' is implicitly deleted because the default definition would be ill-formed:
 1341 |     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1342 |       _Default_ranged_hash, true>
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1341:12: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>::~_Hashtable_ebo_helper()'
In file included from /usr/include/c++/10/unordered_map:46,
                 from swap.cpp:5:
/usr/include/c++/10/bits/hashtable.h:451:7: error: use of deleted function 'std::__detail::_Hashtable_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::equal_to<std::pair<int, int> >, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::~_Hashtable_base()'
  451 |       _Hashtable() = default;
      |       ^~~~~~~~~~
In file included from /usr/include/c++/10/bits/hashtable.h:35,
                 from /usr/include/c++/10/unordered_map:46,
                 from swap.cpp:5:
/usr/include/c++/10/bits/hashtable_policy.h:1725:10: note: 'std::__detail::_Hashtable_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::equal_to<std::pair<int, int> >, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::~_Hashtable_base()' is implicitly deleted because the default definition would be ill-formed:
 1725 |   struct _Hashtable_base
      |          ^~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1725:10: error: use of deleted function 'std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()'
/usr/include/c++/10/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_M_hash_code(const _Key&) const [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code = long unsigned int]':
/usr/include/c++/10/bits/hashtable_policy.h:734:45:   required from 'std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::mapped_type& std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::operator[](std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::key_type&&) [with _Key = std::pair<int, int>; _Pair = std::pair<const std::pair<int, int>, int>; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>; std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::mapped_type = int; std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::key_type = std::pair<int, int>]'
/usr/include/c++/10/bits/unordered_map.h:988:20:   required from 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = int; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type = int; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::key_type = std::pair<int, int>]'
swap.cpp:76:20:   required from here
/usr/include/c++/10/bits/hashtable_policy.h:1377:16: error: static assertion failed: hash function must be invocable with an argument of key type
 1377 |  static_assert(__is_invocable<const _H1&, const _Key&>{},
      |                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1379:16: error: no match for call to '(const std::hash<std::pair<int, int> >) (const std::pair<int, int>&)'
 1379 |  return _M_h1()(__k);
      |         ~~~~~~~^~~~~
In file included from /usr/include/c++/10/unordered_map:46,
                 from swap.cpp:5:
/usr/include/c++/10/bits/hashtable.h: In instantiation of 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::~_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]':
/usr/include/c++/10/bits/unordered_map.h:102:11:   required from here
/usr/include/c++/10/bits/hashtable.h:1389:5: error: use of deleted function 'std::__detail::_Hashtable_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::equal_to<std::pair<int, int> >, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::~_Hashtable_base()'
 1389 |     }
      |     ^