| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1005868 | irmuun | Highway Tolls (IOI18_highway) | C++17 | 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.
#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const int maxn=9e4+5;
int n,m,a,b;
vector<int>u,v;
vector<pair<int,int>>adj[maxn];
vector<int>dep(maxn,0),edge(maxn,0),w,L,R,edges;
int cur=0;
void dfs(int x,int p){
if(cur==0) L.pb(x);
else R.pb(x);
par[x]=p;
for(auto [y,e]:adj[x]){
if(y!=p){
if(cur==0){
edges.pb(e);
}
dep[y]=dep[x]+1;
edge[y]=e;
dfs(y,x);
}
}
}
void find_pair(int N,vector<int>U,vector<int>V,int A, int B){
n=N,u=U,v=V,a=A,b=B;
m=u.size();
w.resize(m);
fill(all(w),0);
ll C=ask(w);
int d=C/A;
int l=0,r=m-1;
while(l<r){
int mid=(l+r)/2;
fill(all(w),0);
for(int i=0;i<=mid;i++){
w[i]=1;
}
if(ask(w)>C){
r=mid;
}
else{
l=mid+1;
}
}
int v1=u[l],v2=v[l];
dep[v1]=0;
dep[v2]=0;
dfs(v1,v2);
cur=1;
dfs(v2,v1);
fill(all(w),0);
for(auto e:edges){
w[e]=1;
}
ll cost=ask(w);
int dep1=(C-cost)/(ll)(b-a);
int dep2=d-dep1;
vector<int>ver;
for(auto i:left){
if(dep[i]==dep1){
ver.pb(i);
}
}
l=0,r=ver.size();
while(l<r){
int mid=(l+r)/2;
fill(all(w),0);
for(int i=0;i<=mid;i++){
w[edge[ver[i]]]=1;
}
if(ask(w)>C){
r=mid;
}
else{
l=mid+1;
}
}
int S=ver[l];
ver.clear();
for(auto i:left){
if(dep[i]==dep2){
ver.pb(i);
}
}
l=0,r=ver.size();
while(l<r){
int mid=(l+r)/2;
fill(all(w),0);
for(int i=0;i<=mid;i++){
w[edge[ver[i]]]=1;
}
if(ask(w)>C){
r=mid;
}
else{
l=mid+1;
}
}
int T=ver[l];
answer(S,T);
return;
}
Compilation message (stderr)
highway.cpp: In function 'void dfs(int, int)':
highway.cpp:25:5: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
25 | par[x]=p;
| ^~~
| __pstl::execution::v1::par
In file included from /usr/include/c++/10/pstl/glue_algorithm_defs.h:15,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from highway.cpp:1:
/usr/include/c++/10/pstl/execution_defs.h:111:27: note: '__pstl::execution::v1::par' declared here
111 | constexpr parallel_policy par{};
| ^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:74:16: error: no matching function for call to 'begin(std::ios_base& (&)(std::ios_base&))'
74 | for(auto i:left){
| ^~~~
In file included from /usr/include/c++/10/bits/range_access.h:36,
from /usr/include/c++/10/string:54,
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 highway.cpp:1:
/usr/include/c++/10/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
90 | begin(initializer_list<_Tp> __ils) noexcept
| ^~~~~
/usr/include/c++/10/initializer_list:90:5: note: template argument deduction/substitution failed:
highway.cpp:74:16: note: mismatched types 'std::initializer_list<_Tp>' and 'std::ios_base& (*)(std::ios_base&)'
74 | for(auto i:left){
| ^~~~
In file included from /usr/include/c++/10/string:54,
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 highway.cpp:1:
/usr/include/c++/10/bits/range_access.h:51:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&)'
51 | begin(_Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/10/bits/range_access.h:51:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&) [with _Container = std::ios_base&(std::ios_base&)]':
highway.cpp:74:16: required from here
/usr/include/c++/10/bits/range_access.h:51:50: error: request for member 'begin' in '__cont', which is of non-class type 'std::ios_base&(std::ios_base&)'
51 | begin(_Container& __cont) -> decltype(__cont.begin())
| ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&)'
61 | begin(const _Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&) [with _Container = std::ios_base&(std::ios_base&)]':
highway.cpp:74:16: required from here
/usr/include/c++/10/bits/range_access.h:61:56: error: request for member 'begin' in '__cont', which is of non-class type 'std::ios_base&(std::ios_base&)'
61 | begin(const _Container& __cont) -> decltype(__cont.begin())
| ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
90 | begin(_Tp (&__arr)[_Nm])
| ^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note: template argument deduction/substitution failed:
highway.cpp:74:16: note: mismatched types '_Tp [_Nm]' and 'std::ios_base&(std::ios_base&)'
74 | for(auto i:left){
| ^~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from highway.cpp:1:
/usr/include/c++/10/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
1214 | begin(valarray<_Tp>& __va)
| ^~~~~
/usr/include/c++/10/valarray:1214:5: note: template argument deduction/substitution failed:
highway.cpp:74:16: note: mismatched types 'std::valarray<_Tp>' and 'std::ios_base&(std::ios_base&)'
74 | for(auto i:left){
| ^~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from highway.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
1224 | begin(const valarray<_Tp>& __va)
| ^~~~~
/usr/include/c++/10/valarray:1224:5: note: template argument deduction/substitution failed:
highway.cpp:74:16: note: mismatched types 'const std::valarray<_Tp>' and 'std::ios_base&(std::ios_base&)'
74 | for(auto i:left){
| ^~~~
highway.cpp:74:16: error: no matching function for call to 'end(std::ios_base& (&)(std::ios_base&))'
In file included from /usr/include/c++/10/bits/range_access.h:36,
from /usr/include/c++/10/string:54,
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 highway.cpp:1:
/usr/include/c++/10/initializer_list:101:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
101 | end(initializer_list<_Tp> __ils) noexcept
| ^~~
/usr/include/c++/10/initializer_list:101:5: note: template argument deduction/substitution failed:
highway.cpp:74:16: note: mismatched types 'std::initializer_list<_Tp>' and 'std::ios_base& (*)(std::ios_base&)'
74 | for(auto i:left){
| ^~~~
In file included from /usr/include/c++/10/string:54,
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 highway.cpp:1:
/usr/include/c++/10/bits/range_access.h:71:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
71 | end(_Container& __cont) -> decltype(__cont.end())
| ^~~
/usr/include/c++/10/bits/range_access.h:71:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&) [with _Container = std::ios_base&(std::ios_base&)]':
highway.cpp:74:16: required from here
/usr/include/c++/10/bits/range_access.h:71:48: error: request for member 'end' in '__cont', which is of non-class type 'std::ios_base&(std::ios_base&)'
71 | end(_Container& __cont) -> decltype(__cont.end())
| ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:81:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
81 | end(const _Container& __cont) -> decltype(__cont.end())
| ^~~
/usr/include/c++/10/bits/range_access.h:81:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&) [with _Container = std::ios_base&(std::ios_base&)]':
highway.cpp:74:16: required from here
/usr/include/c++/10/bits/range_access.h:81:54: error: request for member 'end' in '__cont', which is of non-class type 'std::ios_base&(std::ios_base&)'
81 | end(const _Container& __cont) -> decltype(__cont.end())
| ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:100:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
100 | end(_Tp (&__arr)[_Nm])
| ^~~
/usr/include/c++/10/bits/range_access.h:100:5: note: template argument deduction/substitution failed:
highway.cpp:74:16: note: mismatched types '_Tp [_Nm]' and 'std::ios_base&(std::ios_base&)'
74 | for(auto i:left){
| ^~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from highway.cpp:1:
/usr/include/c++/10/valarray:1234:5: note: candidate: 'template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)'
1234 | end(valarray<_Tp>& __va)
| ^~~
/usr/include/c++/10/valarray:1234:5: note: template argument deduction/substitution failed:
highway.cpp:74:16: note: mismatched types 'std::valarray<_Tp>' and 'std::ios_base&(std::ios_base&)'
74 | for(auto i:left){
| ^~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from highway.cpp:1:
/usr/include/c++/10/valarray:1244:5: note: candidate: 'template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)'
1244 | end(const valarray<_Tp>& __va)
| ^~~
/usr/include/c++/10/valarray:1244:5: note: template argument deduction/substitution failed:
highway.cpp:74:16: note: mismatched types 'const std::valarray<_Tp>' and 'std::ios_base&(std::ios_base&)'
74 | for(auto i:left){
| ^~~~
highway.cpp:95:16: error: no matching function for call to 'begin(std::ios_base& (&)(std::ios_base&))'
95 | for(auto i:left){
| ^~~~
In file included from /usr/include/c++/10/bits/range_access.h:36,
from /usr/include/c++/10/string:54,
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 highway.cpp:1:
/usr/include/c++/10/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
90 | begin(initializer_list<_Tp> __ils) noexcept
| ^~~~~
/usr/include/c++/10/initializer_list:90:5: note: template argument deduction/substitution failed:
highway.cpp:95:16: note: mismatched types 'std::initializer_list<_Tp>' and 'std::ios_base& (*)(std::ios_base&)'
95 | for(auto i:left){
| ^~~~
In file included from /usr/include/c++/10/string:54,
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 highway.cpp:1:
/usr/include/c++/10/bits/range_access.h:51:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&)'
51 | begin(_Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/10/bits/range_access.h:51:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&) [with _Container = std::ios_base&(std::ios_base&)]':
highway.cpp:95:16: required from here
/usr/include/c++/10/bits/range_access.h:51:50: error: request for member 'begin' in '__cont', which is of non-class type 'std::ios_base&(std::ios_base&)'
51 | begin(_Container& __cont) -> decltype(__cont.begin())
| ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&)'
61 | begin(const _Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&) [with _Container = std::ios_base&(std::ios_base&)]':
highway.cpp:95:16: required from here
/usr/include/c++/10/bits/range_access.h:61:56: error: request for member 'begin' in '__cont', which is of non-class type 'std::ios_base&(std::ios_base&)'
61 | begin(const _Container& __cont) -> decltype(__cont.begin())
| ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
90 | begin(_Tp (&__arr)[_Nm])
| ^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note: template argument deduction/substitution failed:
highway.cpp:95:16: note: mismatched types '_Tp [_Nm]' and 'std::ios_base&(std::ios_base&)'
95 | for(auto i:left){
| ^~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from highway.cpp:1:
/usr/include/c++/10/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
1214 | begin(valarray<_Tp>& __va)
| ^~~~~
/usr/include/c++/10/valarray:1214:5: note: template argument deduction/substitution failed:
highway.cpp:95:16: note: mismatched types 'std::valarray<_Tp>' and 'std::ios_base&(std::ios_base&)'
95 | for(auto i:left){
| ^~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from highway.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
1224 | begin(const valarray<_Tp>& __va)
| ^~~~~
/usr/include/c++/10/valarray:1224:5: note: template argument deduction/substitution failed:
highway.cpp:95:16: note: mismatched types 'const std::valarray<_Tp>' and 'std::ios_base&(std::ios_base&)'
95 | for(auto i:left){
| ^~~~
highway.cpp:95:16: error: no matching function for call to 'end(std::ios_base& (&)(std::ios_base&))'
In file included from /usr/include/c++/10/bits/range_access.h:36,
from /usr/include/c++/10/string:54,
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 highway.cpp:1:
/usr/include/c++/10/initializer_list:101:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
101 | end(initializer_list<_Tp> __ils) noexcept
| ^~~
/usr/include/c++/10/initializer_list:101:5: note: template argument deduction/substitution failed:
highway.cpp:95:16: note: mismatched types 'std::initializer_list<_Tp>' and 'std::ios_base& (*)(std::ios_base&)'
95 | for(auto i:left){
| ^~~~
In file included from /usr/include/c++/10/string:54,
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 highway.cpp:1:
/usr/include/c++/10/bits/range_access.h:71:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
71 | end(_Container& __cont) -> decltype(__cont.end())
| ^~~
/usr/include/c++/10/bits/range_access.h:71:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&) [with _Container = std::ios_base&(std::ios_base&)]':
highway.cpp:95:16: required from here
/usr/include/c++/10/bits/range_access.h:71:48: error: request for member 'end' in '__cont', which is of non-class type 'std::ios_base&(std::ios_base&)'
71 | end(_Container& __cont) -> decltype(__cont.end())
| ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:81:5: note: candidate: 'template<class