Submission #467849

#	Time	Username	Problem	Language	Result	Execution time	Memory
467849		nickmet2004	Evacuation plan (IZhO18_plan)	C++11	Compilation error	0 ms	0 KiB

plan

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
typedef pair<int , int> ipair;
const int N = 5e5 + 5;
struct TEdges{
    int u , v , w;
    bool operator>(const TEdges &X) const{
        return w > X.w;
    }
};
int n , m , k , q;
vector<ipair> adj[N];
TEdges E[N];
priority_queue<ipair , vector<ipair> , greater<ipair>> pq;
int d[N] , P[N][20] , depth[N] , mn[N][20] , sz[N] , p[N];
int Find(int x){
    return (x == p[x]) ? x : p[x] = Find(p[x]);
}
int Union(int u , int v){
    int U = Find(u) ,V = Find(v);
    if(U == V) return 0;
    if(sz[U] < sz[V]) swap(U , V);
    sz[U] += sz[V]; p[V] = U;
    return 1;
}
void dfs(int u, int p ){
    P[u][0]= p;
    for(int i = 1; i <= 17; ++i) P[u][i] = P[P[u][u - 1]][i - 1];
    for(int i = 1; i <= 17; ++i)  mn[u][i] = min(mn[u][i - 1] , mn[P[u][i - 1]][i - 1]);
    for(auto X : adj[u]){
        int v = X.f , w = X.s;
        if(v == p) continue;
        mn[v][0] = w;
        depth[v] = depth[u] + 1;
        dfs(v ,u);
    }
}
int LCA(int u, int v){
    int res = 2e9;
    if(depth[u] < depth[v]) swap(u , v);
    int k = depth[u] - depth[v];
    for(int i = 17; ~i; --i){
        if(k>>i&1){ res = min(res , mn[u][i]) ; u= P[u][i];
        }
    }
    if(u == v) return res;
    for(int i = 17; ~i; --i){
        if(P[u][i] != P[v][i]){
            res = min({res , mn[u][i] , mn[v][i]}); u = P[u][i] ; v = P[v][i];
        }
    }
    return min({res , mn[u][0] , mn[v][0]});
}
 main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int u , v , w; cin >> u >> v >> w;
        adj[u].emplace_back(v , w); adj[v].emplace_back(u , w);
        E[i].u = u; E[i].v = v; E[i].w = w;
    }
    cin >> k;
    for(int i = 1; i <= n; ++i) d[i] = 1e18;
    for(int i= 0;i < k; ++i){
        int u; cin >> u;
        d[u] = 0; pq.push({0 , u});
    }
    while(!pq.empty()){
        auto X = pq.top(); pq.pop();
        if(X.f != d[X.s]) continue;
        for(ipair N : adj[X.s]){
            if(d[N.f] > X.f + N.s){
                d[N.f] = X.f + N.s;
                pq.push({d[N.f], N.f});
            }
        }
    }
    for(int i = 0; i < N; ++i) for(int j = 0; j < 20; ++j) mn[i][j] = 1e18;
    //for(int i = 1;i <= n; ++i) cout << d[i] << ' '; cerr << endl;
    for(int i = 1; i <= n; ++i) p[i] = i , sz[i] = 1;///
    for(int i = 0; i < m; ++i) E[i].w = min(d[E[i].u] , d[E[i].v]);
    for(int i = 1; i <= n; ++i) adj[i].clear();///
    sort(E , E + m);
    for(int i = 0; i < m; ++i){
        int u = E[i].u , v = E[i].v ,w = E[i].w;
        if(Union(u , v)){
            adj[u].emplace_back(v , w); adj[v].emplace_back(u , w);
        }
    }
    /*
    for(int i = 0; i < m; ++i) {
        cout << E[i]. u<< " " << E[i].v  << " " << E[i].w << endl;
    }cerr << endl;
    */
    dfs(1 ,0);

    cin >> q;
    while(q--){
        int u , v;
        cin >> u >> v; //--u; --v;
        cout << LCA(u ,v) << endl;
    }

}

Compilation message (stderr)

plan.cpp:57:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 |  main (){
      |  ^~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = TEdges*; _Iterator2 = TEdges*]':
/usr/include/c++/10/bits/stl_algo.h:1846:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = TEdges*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1886:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = TEdges*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1977:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = TEdges*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:4859:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = TEdges*]'
plan.cpp:86:19:   required from here
/usr/include/c++/10/bits/predefined_ops.h:43:23: error: no match for 'operator<' (operand types are 'TEdges' and 'TEdges')
   43 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.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/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:43:23: note:   'TEdges' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   43 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.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/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:43:23: note:   'TEdges' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   43 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = TEdges; _Iterator = TEdges*]':
/usr/include/c++/10/bits/stl_algo.h:1826:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = TEdges*; _Compare = __gnu_cxx::__ops::_Val_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = TEdges*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1886:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = TEdges*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1977:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = TEdges*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:4859:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = TEdges*]'
plan.cpp:86:19:   required from here
/usr/include/c++/10/bits/predefined_ops.h:96:22: error: no match for 'operator<' (operand types are 'TEdges' and 'TEdges')
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.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/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'TEdges' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.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/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'TEdges' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = TEdges*; _Value = TEdges]':
/usr/include/c++/10/bits/stl_heap.h:139:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = TEdges*; _Distance = long int; _Tp = TEdges; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
/usr/include/c++/10/bits/stl_heap.h:246:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = TEdges*; _Distance = long int; _Tp = TEdges; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_heap.h:355:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = TEdges*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1666:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = TEdges*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1937:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = TEdges*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1953:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = TEdges*; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = TEdges*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:4859:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = TEdges*]'
plan.cpp:86:19:   required from here
/usr/include/c++/10/bits/predefined_ops.h:67:22: error: no match for 'operator<' (operand types are 'TEdges' and 'TEdges')
   67 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.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/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note:   'TEdges' 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/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.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/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 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 plan.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note:   'TEdges' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   67 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~