| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 937147 | amirhoseinfar1385 | Harbingers (CEOI09_harbingers) | 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>
using namespace std;
const int maxn=100000+10;
long long inf=1e18,kaf=(1<<17);
struct func{
func(){
fas=shib=-inf;
}
long long fas,shib;
long long inersect(func f){
long long sor=fas-f.fas,makh=f.shib-shib;
if(makh==0){
if(sor>0){
return -inf;
}
return inf;
}
if(makh<0){
makh*=-1;
sor*=-1;
}
if(sor<0){
return sor/makh;
}
return (sor+makh-1)/makh;
}
bool operator <(const func f)const {
return shib<f.shib;
}
}fakefunc;
struct cht{
vector<pair<long long,func>>st;
void add(func f){
while((int)st.size()>0){
int x=f.inersect(st.back().second);
if(x<=st.back().first){
st.pop_back();
continue;
}else{
st.push_back(make_pair(x,f));
break;
}
}
if((int)st.size()==0){
st.push_back(make_pair(-inf,f));
}
}
long long get(int x){
int p=lower_bound(st.begin(),st.end(),make_pair(x+1,fakefunc))-st.begin()-1;
if(p<0){
return -inf;
}
////cout<<st.back().second.fas<<" "<<st.back().second.shib<<" "<<st.back().first<<endl;
return st[p].second.fas+x*st[p].second.shib;
}
};
struct segment{
cht ch[(1<<18)];
void upd(int i,int l,int r,int tl,int tr,func f){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
ch[i].add(f);
return ;
}
int m=(l+r)>>1;
upd((i<<1),l,m,tl,tr,f);
upd((i<<1)^1,m+1,r,tl,tr,f);
}
int pors(int x,int v){
int ret=-inf;
x+=kaf;
while(x>0){
ret=max(ret,ch[x].get(v));
x>>=1;
}
return ret;
}
}seg;
struct yal{
int u,v,w;
int getad(int fu){
return (u^v^fu);
}
}alle[maxn];
int n,timea=0,high[maxn],para[maxn];
long long dp[maxn];
pair<int,int>stf[maxn],all[maxn];
vector<int>adj[maxn];
void dfs(int u,int par=0,int len=0){
timea++;
para[u]=par;
high[u]=len;
stf[u].first=timea;
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v!=par){
dfs(v,u,len+alle[x].w);
}
}
stf[u].second=timea;
}
void vorod(){
cin>>n;
for(int i=0;i<n-1;i++){
cin>>alle[i].u>>alle[i].v>>alle[i].w;
adj[alle[i].u].push_back(i);
adj[alle[i].v].push_back(i);
}
for(int i=2;i<=n;i++){
cin>>all[i].first>>all[i].second;
}
}
void pre(){
dfs(1);
}
void upd(int u){
dp[u]=1ll*min(-seg.pors(stf[u].first,all[u].second),0ll)+all[u].first+1ll*all[u].second*high[u];
func f;
f.fas=-dp[u];
f.shib=high[u];
seg.upd(1,0,kaf-1,stf[u].first,stf[u].second,f);
}
void solve(int u=1){
upd(u);
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v!=para[u]){
solve(v);
}
}
}
void khor(){
for(int i=2;i<=n;i++){
cout<<dp[i]<<" ";
}
cout<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//cout.tie(0);
//freopen("inp.txt","r",stdin);
vorod();
pre();
solve();
khor();
}
Compilation message (stderr)
harbingers.cpp: In member function 'int segment::pors(int, int)':
harbingers.cpp:76:28: error: no matching function for call to 'max(int&, long long int)'
76 | ret=max(ret,ch[x].get(v));
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
harbingers.cpp:76:28: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
76 | ret=max(ret,ch[x].get(v));
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
harbingers.cpp:76:28: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
76 | ret=max(ret,ch[x].get(v));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from harbingers.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
harbingers.cpp:76:28: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
76 | ret=max(ret,ch[x].get(v));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from harbingers.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
harbingers.cpp:76:28: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
76 | ret=max(ret,ch[x].get(v));
| ^
harbingers.cpp: In function 'void upd(int)':
harbingers.cpp:125:57: error: no matching function for call to 'min(int, long long int)'
125 | dp[u]=1ll*min(-seg.pors(stf[u].first,all[u].second),0ll)+all[u].first+1ll*all[u].second*high[u];
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
harbingers.cpp:125:57: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
125 | dp[u]=1ll*min(-seg.pors(stf[u].first,all[u].second),0ll)+all[u].first+1ll*all[u].second*high[u];
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
harbingers.cpp:125:57: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
125 | dp[u]=1ll*min(-seg.pors(stf[u].first,all[u].second),0ll)+all[u].first+1ll*all[u].second*high[u];
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from harbingers.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
harbingers.cpp:125:57: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
125 | dp[u]=1ll*min(-seg.pors(stf[u].first,all[u].second),0ll)+all[u].first+1ll*all[u].second*high[u];
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from harbingers.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
harbingers.cpp:125:57: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
125 | dp[u]=1ll*min(-seg.pors(stf[u].first,all[u].second),0ll)+all[u].first+1ll*all[u].second*high[u];
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<long long int, func>*, std::vector<std::pair<long long int, func> > >; _Value = const std::pair<int, func>]':
/usr/include/c++/10/bits/stl_algobase.h:1324:14: required from '_ForwardIterator std::__lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<long long int, func>*, std::vector<std::pair<long long int, func> > >; _Tp = std::pair<int, func>; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
/usr/include/c++/10/bits/stl_algobase.h:1359:32: required from '_ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<long long int, func>*, std::vector<std::pair<long long int, func> > >; _Tp = std::pair<int, func>]'
harbingers.cpp:49:64: required from here
/usr/include/c++/10/bits/predefined_ops.h:67:22: error: no match for 'operator<' (operand types are 'std::pair<long long int, func>' and 'const std::pair<int, func>')
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
1096 | operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, func>' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
1104 | operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, func>' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from harbingers.cpp:1:
/usr/include/c++/10/bits/regex.h:1075:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
1075 | operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1075:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, func>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from harbingers.cpp:1:
/usr/include/c++/10/bits/regex.h:1156:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
1156 | operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1156:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, func>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from harbingers.cpp:1:
/usr/include/c++/10/bits/regex.h:1249:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
1249 | operator<(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1249:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, func>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from harbingers.cpp:1:
/usr/include/c++/10/bits/regex.h:1323:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
1323 | operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1323:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'const std::pair<int, func>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from harbingers.cpp:1:
/usr/include/c++/10/bits/regex.h:1417:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
1417 | operator<(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1417:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, func>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from harbingers.cpp:1:
/usr/include/c++/10/bits/regex.h:1492:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
1492 | operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1492:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'const std::pair<int, func>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from harbingers.cpp:1:
/usr/include/c++/10/bits/regex.h:1592:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
1592 | operator<(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1592:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, func>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from harbingers.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:489:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const s