Submission #878601

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
878601	2023-11-24T21:55:13 Z	cpptowin	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KB

factories

#include"factories.h"
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define fi first
#define se second
#define pb emplace_back
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define vi vector<int>
using namespace std;
vii ke[maxn];
int par[maxn][20],sz[maxn];
long long d[maxn];
int ind[maxn],head[maxn],cnt = 1;
long long minn[maxn][20];
vector<array<long long,4>> adj;
void dfs(int u,int parent)
{
    sz[u] = 1;
    for(auto [v,w] : ke[u])
    {
        if(v == parent) continue;
        par[v][0] = u;
        d[v] = d[u] + w;
        dfs(v,u);
        sz[u] += sz[v];
    }
}
void hld(int u,int parent)
{
    if(head[cnt] == 0) head[cnt] = u;
    ind[u] = cnt;
    int  sc = -1,maxx = -1;
    for(auto [v,w] : ke[u]) if(v != parent)
        {
            if(maxx < sz[v])
            {
                maxx = sz[v];
                sc = v;
            }
        }
    if(sc != -1) hld(sc,u);
    for(auto [v,w] : ke[u]) if(v != parent and v != sc)
        {
            cnt++;
            hld(v,u);
        }
}
void get(int u,int t)
{
    long long val = d[u];
    int uchain,vchain = ind[1];
    while(1)
    {
        uchain = ind[u];
        adj.push_back({(long long)uchain,(long long)u,val,(long long)t});
        if(uchain == vchain) return;
        u = ind[u];
        u = par[head[u]][0];
    }
}
void Init(int N,int A[],int B[],int D[])
{
    fo(i,0,N - 2)
    {
        ke[A[i] + 1].pb(B[i] + 1,D[i]);
        ke[B[i] + 1].pb(A[i] + 1,D[i]);
    }
    dfs(1,1);
    hld(1,1);
}
long long Query(int S, int X[], int T, int Y[])
{
    long long ans = 2e18;
    fo(i,0,S - 1) get(X[i] + 1,0);
    fo(i,0,T - 1) get(Y[i] + 1,1);
    sort(adj.begin(),adj.end(),[](array<int,4> a,array<int,4> b)
    {
        return d[a[1]] > d[b[1]];
    });
    fo(i,1,cnt) fo(j,0,1) minn[i][j] = 2e18;
    for(auto [p,v,dist,t] : adj)
    {
        ans = min(ans,minn[p][1 - t] - 2 * d[v] + dist);
        minn[p][t] = min(minn[p][t],dist);
    }
    adj.clear();
    return ans;
}

Compilation message

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 factories.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>]':
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>]'
factories.cpp:83:6:   required from here
/usr/include/c++/10/bits/predefined_ops.h:156:30: error: no match for call to '(Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>) (std::array<long long int, 4>&, std::array<long long int, 4>&)'
  156 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h:156:30: note: candidate: 'bool (*)(std::array<int, 4>, std::array<int, 4>)' (conversion)
/usr/include/c++/10/bits/predefined_ops.h:156:30: note:   candidate expects 3 arguments, 3 provided
factories.cpp:80:32: note: candidate: 'Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>'
   80 |     sort(adj.begin(),adj.end(),[](array<int,4> a,array<int,4> b)
      |                                ^
factories.cpp:80:32: note:   no known conversion for argument 1 from 'array<long long int,[...]>' to 'array<int,[...]>'
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 factories.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = std::array<long long int, 4>; _Iterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>]':
/usr/include/c++/10/bits/stl_algo.h:1826:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:1886:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:1977:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>]'
factories.cpp:83:6:   required from here
/usr/include/c++/10/bits/predefined_ops.h:238:23: error: no match for call to '(Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>) (std::array<long long int, 4>&, std::array<long long int, 4>&)'
  238 |  { return bool(_M_comp(__val, *__it)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h:238:23: note: candidate: 'bool (*)(std::array<int, 4>, std::array<int, 4>)' (conversion)
/usr/include/c++/10/bits/predefined_ops.h:238:23: note:   candidate expects 3 arguments, 3 provided
factories.cpp:80:32: note: candidate: 'Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>'
   80 |     sort(adj.begin(),adj.end(),[](array<int,4> a,array<int,4> b)
      |                                ^
factories.cpp:80:32: note:   no known conversion for argument 1 from 'array<long long int,[...]>' to 'array<int,[...]>'
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 factories.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Value = std::array<long long int, 4>; _Compare = Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>]':
/usr/include/c++/10/bits/stl_heap.h:139:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Distance = long int; _Tp = std::array<long long int, 4>; _Compare = __gnu_cxx::__ops::_Iter_comp_val<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_heap.h:246:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Distance = long int; _Tp = std::array<long long int, 4>; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_heap.h:355:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:1666:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:1937:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:1953:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::array<long long int, 4>*, std::vector<std::array<long long int, 4> > >; _Compare = Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>]'
factories.cpp:83:6:   required from here
/usr/include/c++/10/bits/predefined_ops.h:194:23: error: no match for call to '(Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>) (std::array<long long int, 4>&, std::array<long long int, 4>&)'
  194 |  { return bool(_M_comp(*__it, __val)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h:194:23: note: candidate: 'bool (*)(std::array<int, 4>, std::array<int, 4>)' (conversion)
/usr/include/c++/10/bits/predefined_ops.h:194:23: note:   candidate expects 3 arguments, 3 provided
factories.cpp:80:32: note: candidate: 'Query(int, int*, int, int*)::<lambda(std::array<int, 4>, std::array<int, 4>)>'
   80 |     sort(adj.begin(),adj.end(),[](array<int,4> a,array<int,4> b)
      |                                ^
factories.cpp:80:32: note:   no known conversion for argument 1 from 'array<long long int,[...]>' to 'array<int,[...]>'