Submission #923508

#TimeUsernameProblemLanguageResultExecution timeMemory
923508noyancanturkOlympic Bus (JOI20_ho_t4)C++17
Compilation error
0 ms0 KiB
#ifndef Local #pragma GCC optimize("O3,unroll-loops") const int lim=2e5+5; #else const int lim=3e3+3; #endif #include "bits/stdc++.h" using namespace std; #define int __uint128_t #define pb push_back //const int mod=1e9+7; const int mod=(1ll<<61)-1; using pii=pair<int,int>; struct edge{ int x,y,c,d; }; template <> struct std::hash<pii>{ size_t operator()(const pii& k) const{ return hash<int>()(k.first^(k.second<<10)); } }; const int inf=LLONG_MAX; inline void solve(){ int n,m; cin>>n>>m; edge all[m]; for(int i=0;i<m;i++){ cin>>all[i].x>>all[i].y>>all[i].c>>all[i].d; all[i].x--,all[i].y--; } int dist[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ dist[i][j]=inf; } } for(int i=0;i<m;i++){ dist[all[i].x][all[i].y]=min( all[i].c, dist[all[i].x][all[i].y] ); } for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ dist[i][j]=min( dist[i][j], dist[i][k]+dist[k][j] ); } } } unordered_set<pii>v[n]; for(int i=0;i<m;i++){ v[all[i].x].insert(pii(all[i].y,all[i].c)); } int ans=dist[0][n-1]+dist[n-1][0]; //cerr<<ans<<"\n"; for(auto[x,y,c,d]:all){ //cerr<<x<<" "<<y<<" "<<c<<" "<<dist[y][x]<<"\n"; if(dist[y][x]<=c)continue; // better upperbound exists v[x].erase({y,c}); v[y].insert({x,c}); int curd[n]; for(int i=0;i<n;i++){ curd[i]=inf; } curd[0]=0; bool vis[n]; memset(vis,0,sizeof(vis)); for(int i=0;i<n-1;i++){ int mini=-1; for(int j=0;j<n;j++){ if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){ mini=j; } } vis[mini]=1; if(mini==n-1)break; for(pii ed:v[mini]){ curd[ed.first]=min( curd[ed.first], curd[mini]+ed.second ); } } if(curd[n-1]==inf){ v[y].erase({x,c}); v[x].insert({y,c}); continue; } //for(int i=0;i<n;i++)cerr<<curd[i]<<" "; //cerr<<"\n"; int ansnow=curd[n-1]; for(int i=0;i<n;i++){ curd[i]=inf; } curd[n-1]=0; memset(vis,0,sizeof(vis)); for(int i=0;i<n-1;i++){ int mini=-1; for(int j=0;j<n;j++){ if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){ mini=j; } } vis[mini]=1; if(!mini)break; for(pii ed:v[mini]){ curd[ed.first]=min( curd[ed.first], curd[mini]+ed.second ); } } //for(int i=0;i<n;i++)cerr<<curd[i]<<" "; //cerr<<"\n"; if(curd[0]!=inf){ ansnow+=curd[0]+d; ans=min(ans,ansnow); } //cerr<<ansnow<<"\n\n"; v[y].erase({x,c}); v[x].insert({y,c}); } if(ans<inf-100)cout<<ans<<"\n"; else cout<<"-1\n"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); #ifdef Local freopen(".in","r",stdin); freopen(".out","w",stdout); #else #endif int t=1; //cin>>t; while (t--) { solve(); } }

Compilation message (stderr)

ho_t4.cpp: In member function 'std::size_t std::hash<std::pair<__int128 unsigned, __int128 unsigned> >::operator()(const pii&) const':
ho_t4.cpp:25:22: error: use of deleted function 'std::hash<__int128 unsigned>::hash()'
   25 |     return hash<int>()(k.first^(k.second<<10));
      |                      ^
In file included from /usr/include/c++/10/string_view:42,
                 from /usr/include/c++/10/bits/basic_string.h:48,
                 from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/bits/functional_hash.h:101:12: note: 'std::hash<__int128 unsigned>::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<__int128 unsigned, 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 = __int128 unsigned; 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 = __int128 unsigned; 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();
      |       ^
ho_t4.cpp: In function 'void solve()':
ho_t4.cpp:32:8: error: no match for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and '__int128 unsigned')
   32 |     cin>>n>>m;
      |     ~~~^~~
      |     |    |
      |     |    __int128 unsigned
      |     std::istream {aka std::basic_istream<char>}
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:120:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__istream_type& (*)(std::basic_istream<_CharT, _Traits>::__istream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  120 |       operator>>(__istream_type& (*__pf)(__istream_type&))
      |       ^~~~~~~~
/usr/include/c++/10/istream:120:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: invalid conversion from '__int128 unsigned' to 'std::basic_istream<char>::__istream_type& (*)(std::basic_istream<char>::__istream_type&)' {aka 'std::basic_istream<char>& (*)(std::basic_istream<char>&)'} [-fpermissive]
   32 |     cin>>n>>m;
      |          ^
      |          |
      |          __int128 unsigned
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:124:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__ios_type& (*)(std::basic_istream<_CharT, _Traits>::__ios_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>; std::basic_istream<_CharT, _Traits>::__ios_type = std::basic_ios<char>]' (near match)
  124 |       operator>>(__ios_type& (*__pf)(__ios_type&))
      |       ^~~~~~~~
/usr/include/c++/10/istream:124:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: invalid conversion from '__int128 unsigned' to 'std::basic_istream<char>::__ios_type& (*)(std::basic_istream<char>::__ios_type&)' {aka 'std::basic_ios<char>& (*)(std::basic_ios<char>&)'} [-fpermissive]
   32 |     cin>>n>>m;
      |          ^
      |          |
      |          __int128 unsigned
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:131:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::ios_base& (*)(std::ios_base&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  131 |       operator>>(ios_base& (*__pf)(ios_base&))
      |       ^~~~~~~~
/usr/include/c++/10/istream:131:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: invalid conversion from '__int128 unsigned' to 'std::ios_base& (*)(std::ios_base&)' [-fpermissive]
   32 |     cin>>n>>m;
      |          ^
      |          |
      |          __int128 unsigned
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:168:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  168 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:168:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'bool&' to an rvalue of type 'bool'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:172:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  172 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/10/istream:172:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'short int&' to an rvalue of type 'short int'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:175:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  175 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:175:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'short unsigned int&' to an rvalue of type 'short unsigned int'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:179:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  179 |       operator>>(int& __n);
      |       ^~~~~~~~
/usr/include/c++/10/istream:179:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:182:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  182 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:182:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'unsigned int&' to an rvalue of type 'unsigned int'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:186:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  186 |       operator>>(long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:186:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'long int&' to an rvalue of type 'long int'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:190:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  190 |       operator>>(unsigned long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:190:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'long unsigned int&' to an rvalue of type 'long unsigned int'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:195:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  195 |       operator>>(long long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:195:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'long long int&' to an rvalue of type 'long long int'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:199:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  199 |       operator>>(unsigned long long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:199:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'long long unsigned int&' to an rvalue of type 'long long unsigned int'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:214:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  214 |       operator>>(float& __f)
      |       ^~~~~~~~
/usr/include/c++/10/istream:214:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'float&' to an rvalue of type 'float'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:218:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  218 |       operator>>(double& __f)
      |       ^~~~~~~~
/usr/include/c++/10/istream:218:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'double&' to an rvalue of type 'double'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:222:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  222 |       operator>>(long double& __f)
      |       ^~~~~~~~
/usr/include/c++/10/istream:222:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: cannot bind non-const lvalue reference of type 'long double&' to an rvalue of type 'long double'
   32 |     cin>>n>>m;
      |          ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:235:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  235 |       operator>>(void*& __p)
      |       ^~~~~~~~
/usr/include/c++/10/istream:235:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: invalid conversion from '__int128 unsigned' to 'void*' [-fpermissive]
   32 |     cin>>n>>m;
      |          ^
      |          |
      |          __int128 unsigned
ho_t4.cpp:32:10: error: cannot bind rvalue '(void*)((long int)n)' to 'void*&'
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t4.cpp:8:
/usr/include/c++/10/istream:259:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__streambuf_type*) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__streambuf_type = std::basic_streambuf<char>]' (near match)
  259 |       operator>>(__streambuf_type* __sb);
      |       ^~~~~~~~
/usr/include/c++/10/istream:259:7: note:   conversion of argument 1 would be ill-formed:
ho_t4.cpp:32:10: error: invalid conversion from '__int128 unsigned' to 'std::basic_istream<char>::__streambuf_type*' {aka 'std::basic_streambuf<char>*'} [-fpermissive]
   32 |     cin>>n>>m;
      |          ^
      |          |
      |          __int128 unsigned
ho_t4.cpp:32:8: note: candidate: 'operator>>(int,