Submission #284924

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
284924	2020-08-28T08:02:08 Z	BeanZ	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KB

factories

#include <bits/stdc++.h>
#include "factories.h"


using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int lg = 20;
vector<pair<ll, ll>> node[N];
vector<ll> adj[N];
ll dp[N][21], dep[N];
long long dis[N][21];
ll sz[N];
ll par[N];
long long ans[N];
ll a[N];
bool ok[N], in[N];
void dfs(ll u, ll p){
        for (int i = 1; i <= lg; i++) dp[u][i] = dp[dp[u][i - 1]][i - 1];
        for (int i = 1; i <= lg; i++) dis[u][i] = dis[dp[u][i - 1]][i - 1] + dis[u][i - 1];
        for (auto j : node[u]){
                if (j.first == p) continue;
                dp[j.first][0] = u;
                dis[j.first][0] = j.second;
                dep[j.first] = dep[u] + 1;
                dfs(j.first, u);
        }
}
ll findnewCT(ll u, ll p, ll S){
        for (auto j : adj[u]){
                if (j == p || in[j]) continue;
                if ((sz[j] * 2) >= S) return findnewCT(j, u, S);
        }
        return u;
}
void initsz(ll u, ll p){
        sz[u] = 1;
        for (auto j : adj[u]){
                if (j == p || in[j]) continue;
                initsz(j, u);
                sz[u] += sz[j];
        }
}
ll findCT(ll u, ll S){
        initsz(u, u);
        u = findnewCT(u, u, S);
        in[u] = 1;
        for (auto j : adj[u]){
                if (in[j]) continue;
                if (sz[j] > sz[u]){
                        ll x = findCT(j, S - sz[u]);
                        par[x] = u;
                } else {
                        ll x = findCT(j, sz[j]);
                        par[x] = u;
                }
        }
        return u;
}
ll LCA(ll u, ll v){
        if (dep[u] > dep[v]) swap(u, v);
        ll dist = dep[v] - dep[u];
        for (int i = lg; i >= 0; i--){
                if (dist & (1 << i)) v = dp[v][i];
        }
        if (u == v) return u;
        for (int i = lg; i >= 0; i--){
                if (dp[u][i] != dp[v][i]){
                        u = dp[u][i];
                        v = dp[v][i];
                }
        }
        return dp[u][0];
}
long long cal(ll u, ll lca){
        ll dist = dep[u] - dep[lca];
        ll res = 0;
        for (int i = lg; i >= 0; i--){
                if (dist & (1 << i)){
                        res += dis[u][i];
                        u = dp[u][i];
                }
        }
        return res;
}
long long dist(ll u, ll v){
        ll lca = LCA(u, v);
        return cal(u, lca) + cal(v, lca);
}
vector<ll> recover;
void upd(ll u, ll root){
        if (!ok[u]) recover.push_back(u), ok[u] = 1;
        if (u == 0) return;
        ans[u] = min(ans[u], dist(root, u));
        upd(par[u], root);
}
long long get(ll u, ll root){
        if (u == 0) return 1e16;
        return min(ans[u] + dist(u, root), get(par[u], root));
}
long long Query(int S, int X[], int T, int Y[]){
        recover.clear();
        for (int i = 1; i <= T; i++){
                upd(Y[i - 1] + 1, Y[i - 1] + 1);
        }
        long long res = 1e18;
        for (int i = 1; i <= S; i++){
                res = min(res, get(X[i - 1] + 1, X[i - 1] + 1));
        }
        for (auto j : recover) ans[j] = 1e18, ok[j] = 0;
        return res;
}
void Init(int n, int A[], int B[], int D[]){
        for (int i = 1; i < n; i++){
                node[A[i - 1] + 1].push_back({B[i - 1] + 1, D[i - 1]});
                node[B[i - 1] + 1].push_back({A[i - 1] + 1, D[i - 1]});
                adj[A[i - 1] + 1].insert(B[i - 1] + 1);
                adj[B[i - 1] + 1].insert(A[i - 1] + 1);
        }
        dfs(1, 1);
        ll root = findCT(1, n);
        for (int i = 1; i <= n; i++) ans[i] = 1e18;
}
/*
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("VietCT.INP", "r")){
                freopen("VietCT.INP", "r", stdin);
                freopen("VietCT.OUT", "w", stdout);
        }

}
*/
/*
*/

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:120:54: error: no matching function for call to 'std::vector<long long int>::insert(int)'
  120 |                 adj[A[i - 1] + 1].insert(B[i - 1] + 1);
      |                                                      ^
In file included from /usr/include/c++/9/vector:72,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from factories.cpp:1:
/usr/include/c++/9/bits/vector.tcc:130:5: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, const value_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = long long int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const long long int*, std::vector<long long int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const long long int*; std::vector<_Tp, _Alloc>::value_type = long long int]'
  130 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/vector.tcc:130:5: note:   candidate expects 2 arguments, 1 provided
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from factories.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:1290:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = long long int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const long long int*, std::vector<long long int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const long long int*; std::vector<_Tp, _Alloc>::value_type = long long int]'
 1290 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1290:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1307:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::initializer_list<_Tp>) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = long long int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const long long int*, std::vector<long long int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const long long int*]'
 1307 |       insert(const_iterator __position, initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1307:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1332:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = long long int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const long long int*, std::vector<long long int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const long long int*; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = long long int]'
 1332 |       insert(const_iterator __position, size_type __n, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1332:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1376:2: note: candidate: 'template<class _InputIterator, class> std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, _InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = long long int; _Alloc = std::allocator<long long int>]'
 1376 |  insert(const_iterator __position, _InputIterator __first,
      |  ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1376:2: note:   template argument deduction/substitution failed:
factories.cpp:120:54: note:   candidate expects 3 arguments, 1 provided
  120 |                 adj[A[i - 1] + 1].insert(B[i - 1] + 1);
      |                                                      ^
factories.cpp:121:54: error: no matching function for call to 'std::vector<long long int>::insert(int)'
  121 |                 adj[B[i - 1] + 1].insert(A[i - 1] + 1);
      |                                                      ^
In file included from /usr/include/c++/9/vector:72,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from factories.cpp:1:
/usr/include/c++/9/bits/vector.tcc:130:5: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, const value_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = long long int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const long long int*, std::vector<long long int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const long long int*; std::vector<_Tp, _Alloc>::value_type = long long int]'
  130 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/vector.tcc:130:5: note:   candidate expects 2 arguments, 1 provided
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from factories.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:1290:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = long long int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const long long int*, std::vector<long long int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const long long int*; std::vector<_Tp, _Alloc>::value_type = long long int]'
 1290 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1290:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1307:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::initializer_list<_Tp>) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = long long int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const long long int*, std::vector<long long int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const long long int*]'
 1307 |       insert(const_iterator __position, initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1307:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1332:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = long long int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const long long int*, std::vector<long long int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const long long int*; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = long long int]'
 1332 |       insert(const_iterator __position, size_type __n, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1332:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1376:2: note: candidate: 'template<class _InputIterator, class> std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, _InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = long long int; _Alloc = std::allocator<long long int>]'
 1376 |  insert(const_iterator __position, _InputIterator __first,
      |  ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1376:2: note:   template argument deduction/substitution failed:
factories.cpp:121:54: note:   candidate expects 3 arguments, 1 provided
  121 |                 adj[B[i - 1] + 1].insert(A[i - 1] + 1);
      |                                                      ^
factories.cpp:124:12: warning: unused variable 'root' [-Wunused-variable]
  124 |         ll root = findCT(1, n);
      |            ^~~~