Submission #936441

#TimeUsernameProblemLanguageResultExecution timeMemory
936441HorizonWestCat Exercise (JOI23_ho_t4)C++17
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; vector <vector<int>> v; struct DSUF{ vector<ll> P; ll fs(ll node){ if(P[node]==node) return node; return P[node]=fs(P[node]); } void us(ll a, ll b){ a=fs(a);b=fs(b); if(a!=b) P[b]=a; } DSUF(ll n){ P.assign(n+5,0); for(int i=0; i<P.size(); i++) P[i]=i; } }; vector<ll> g[200001], v(200001,0),G[200001]; ll bl[22][200001]; void dfs(ll node) { for(int j=1; j<22; j++) bl[j][node]=bl[j-1][bl[j-1][node]]; for(auto i:G[node]) if(v[i]==0){ v[i]=v[node]+1; bl[0][i]=node; dfs(i); } } ll cost(ll a, ll b) { if(v[a]<v[b]) swap(a,b); ll cost=v[a]-v[b]; for(int i=21; i>-1; i--) if((cost&(1<<i))!=0) a=bl[i][a]; for(int i=21; i>-1; i--) { if(bl[i][a]!=bl[i][b]) { a=bl[i][a]; b=bl[i][b]; cost+=(1<<i)*2; } } if(a!=b) cost+=2; return cost; } struct LowerCommonAncestor { vector <int> L, E, H; int idx, n; void dfs(int cur, int depth, int parent) { H[cur] = idx; E[idx] = cur; L[idx++] = depth; for (auto& u : v[cur]) if(u != parent) { dfs(u, depth + 1, cur); E[idx] = cur; L[idx++] = depth; } } vector <int> tree; int l; int query(int node, int x, int y, int s, int e) { if (x > e || y < s) return 0; if (s >= x && e <= y) return tree[node]; int middle = (s + e) / 2; int id1 = query(node * 2, x, y, s, middle), id2 = query(node * 2 + 1, x, y, middle + 1, e); return (L[id1] > L[id2] ? id2 : id1); } int query(int i, int j) { return query(1, i, j, 1, l); } void Segment_tree(int n) { for (l = 1; l < n; l = (l << 1)); tree.assign(2 * l, 0); L[0] = Inf; for (int i = 0; i < n; i++) tree[i + l] = i + 1; for (int i = l - 1; i > 0; i--) { tree[i] = (L[tree[2 * i]] > L[tree[2 * i + 1]] ? tree[2 * i + 1] : tree[2 * i]); } } int Ancestor(int i, int j) { int a = min(H[i], H[j]), b = max(H[i], H[j]); return E[query(a, b)]; } int Dist(int x) { return L[H[x]]; } int sol(int i, int j) { int g = Ancestor(i, j); return (Dist(i) + Dist(j) - (2 * Dist(g))); } LowerCommonAncestor(int lenght, int x) { n = lenght; idx = 1; L.assign(2 * n, -1); E.assign(2 * n, -1); H.assign(2 * n, -1); dfs(x, 0, 0); Segment_tree(2*n-2); //RMQ(); } }; int main() { ll n; cin>>n; v.assign(n+1, vector <int> ()); pair<ll,ll> cad[n]; DSUF asd(n+2); for(int i=0; i<n; i++) { cin>>cad[i].first; cad[i].second=i+1; } for(int i=0; i<n-1; i++) { ll a,b; cin>>a>>b; if(cad[a-1].first<cad[b-1].first) swap(a,b); g[a].push_back(b); G[a].push_back(b); G[b].push_back(a); v[a].push_back(b); v[b].push_back(a); } LowerCommonAncestor D(n, 1); sort(cad,cad+n); ll sol[n+2]={ }; for(int i=0; i<n; i++) { pair<ll,ll> temp=cad[i]; for(auto i:g[temp.second]) { sol[temp.second]=max(sol[temp.second],sol[asd.fs(i)]+D.sol(temp.second,asd.fs(i))); asd.us(temp.second,i); } } cout<<sol[cad[n-1].second]; }

Compilation message (stderr)

Main.cpp: In constructor 'DSUF::DSUF(ll)':
Main.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for(int i=0; i<P.size(); i++)
      |                      ~^~~~~~~~~
Main.cpp: At global scope:
Main.cpp:23:23: error: conflicting declaration 'std::vector<long long int> v'
   23 | vector<ll> g[200001], v(200001,0),G[200001];
      |                       ^
Main.cpp:5:22: note: previous declaration as 'std::vector<std::vector<int> > v'
    5 | vector <vector<int>> v;
      |                      ^
Main.cpp: In function 'void dfs(ll)':
Main.cpp:30:16: error: no match for 'operator==' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} and 'int')
   30 |         if(v[i]==0){
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from Main.cpp:1:
/usr/include/c++/10/bits/regex.h:1035:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
 1035 |     operator==(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1035:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   30 |         if(v[i]==0){
      |                  ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from Main.cpp:1:
/usr/include/c++/10/bits/regex.h:1131: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>&)'
 1131 |     operator==(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1131:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   30 |         if(v[i]==0){
      |                  ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from Main.cpp:1:
/usr/include/c++/10/bits/regex.h:1206: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>&)'
 1206 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1206:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   30 |         if(v[i]==0){
      |                  ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from Main.cpp:1:
/usr/include/c++/10/bits/regex.h:1298: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>&)'
 1298 |     operator==(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1298:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
   30 |         if(v[i]==0){
      |                  ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from Main.cpp:1:
/usr/include/c++/10/bits/regex.h:1373: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*)'
 1373 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1373:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   30 |         if(v[i]==0){
      |                  ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from Main.cpp:1:
/usr/include/c++/10/bits/regex.h:1466: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>&)'
 1466 |     operator==(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1466:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
   30 |         if(v[i]==0){
      |                  ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from Main.cpp:1:
/usr/include/c++/10/bits/regex.h:1545: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&)'
 1545 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1545:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   30 |         if(v[i]==0){
      |                  ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from Main.cpp:1:
/usr/include/c++/10/bits/regex.h:2101:5: note: candidate: 'template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator==(const std::__cxx11::match_results<_BiIter, _Alloc>&, const std::__cxx11::match_results<_BiIter, _Alloc>&)'
 2101 |     operator==(const match_results<_Bi_iter, _Alloc>& __m1,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:2101:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
   30 |         if(v[i]==0){
      |                  ^
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 Main.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:466:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator==(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  466 |     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:466:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::pair<_T1, _T2>'
   30 |         if(v[i]==0){
      |                  ^
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 Main.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:360:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  360 |     operator==(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:360:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
   30 |         if(v[i]==0){
      |                  ^
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 Main.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:398:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  398 |     operator==(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:398:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
   30 |         if(v[i]==0){
      |                  ^
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 Main.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1427:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1427 |     operator==(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1427:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::move_iterator<_IteratorL>'
   30 |         if(v[i]==0){
      |                  ^
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 Main.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1495:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
 1495 |     operator==(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1495:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::move_iterator<_IteratorL>'
   30 |         if(v[i]==0){
      |                  ^
In file included from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 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 Main.cpp:1:
/usr/include/c++/10/bits/postypes.h:222:5: note: candidate: 'template<class _StateT> bool std::operator==(const std::fpos<_StateT>&, const std::fpos<_StateT>&)'
  222 |     operator==(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/postypes.h:222:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::fpos<_StateT>'
   30 |         if(v[i]==0){
      |                  ^
In file included from /usr/include/c++/10/string:41,
                 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 Main.cpp:1:
/usr/include/c++/10/bits/allocator.h:206:5: note: candidate: 'template<class _T1, class _T2> bool std::operator==(const std::allocator<_CharT>&, const std::allocator<_T2>&)'
  206 |     operator==(const allocator<_T1>&, const allocator<_T2>&)
      |     ^~~~~~~~
/usr/include/c++/10/bits/allocator.h:206:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} is not derived from 'const std::allocator<_CharT>'
   30 |         if(v[i]==0){
      |                  ^
In file included 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 Main.cpp:1:
/usr/include/c++/10/string_view:490:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator==(std::basic_string_view<_CharT, _Traits>, std::basic_string_view<_CharT, _Traits>)'
  490 |     operator==(basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:490:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   'std::vector<int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
   30 |         if(v[i]==0){
      |                  ^
In file included 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 Main.cpp:1:
/usr/include/c++/10/string_view:496:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator==(std::basic_string_view<_CharT, _Traits>, std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >)'
  496 |     operator==(basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:496:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   'std::vector<int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
   30 |         if(v[i]==0){
      |                  ^
In file included 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 Main.cpp:1:
/usr/include/c++/10/string_view:519:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator==(std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >, std::basic_string_view<_CharT, _Traits>)'
  519 |     operator==(__type_identity_t<basic_string_view<_CharT, _Traits>> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:519:5: note:   template argument deduction/substitution failed:
Main.cpp:30:18: note:   mismatched types 'std::basic_string_view<_CharT, _Traits>' and 'int'
   30 |         if(v[i]==0){
      |                  ^
In file included 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 Main.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6153:5: note: candidate: 'template<class _CharT, class _Trai