oj.uz

Submission #892866

# Submission time Handle Problem Language Result Execution time Memory
892866 2023-12-26T05:54:13 Z eysbutno Crocodile's Underground City (IOI11_crocodile) C++11
Compilation error
 0 ms 0 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define pb push_back
#define ins insert
#define f first 
#define s second 

const int MX = 1e5;
const ll INF = 1e18;
vector<pii> adj[MX];
ll dist[MX], fin[MX];
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, m, k; cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int x, y, w; 
        cin >> x >> y >> w;
        adj[x].pb({y, w});
        adj[y].pb({x, w});
    }
    for (int i = 0; i < n; i++) {
        dist[i] = INF, fin[i] = INF;
    }
    vector<int> st(k);
    priority_queue<pll> pq;
    for (int i = 0; i < k; i++) {
        int x; cin >> x;
        pq.push({0, x});
        st[i] = x;
        dist[x] = 0;
    }
    while (!pq.empty()) {
        auto N = pq.top(); pq.pop();
        ll t = -N.f, u = N.s;
        if (dist[u] != t) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }
    fin[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto N = pq.top(); pq.pop();
        ll t = -N.f, u = N.s;
        if (fin[u] != t) continue;
        vector<vector<ll>> pos;
        for (auto [v, w] : adj[u]) {
            pos.pb({w + dist[v], v, w});
        }
        sort(all(pos), [&](auto& x, auto& y) {
            return x[0] < y[0];
        });
        for (int i = 1; i < sz(pos); i++) {
            ll v = pos[i][1], w = pos[i][2];
            if (t + w < fin[v]) {
                fin[v] = t + w;
                pq.push({-fin[v], v});
            }
        }
    }
    ll res = 2e9;
    for (int i : st) {
        smin(res, fin[i]);
    }
    cout << res << '\n';
    auto test = [&]() {
        for (int i = 0; i < n; i++) {
            cout << i << ": " << fin[i] << '\n';
        }
    };
    // test();
}
/**
 * Problem: IOI, Crocodile.
 * Observations:
 * 1. You will never try to go
 * backwards, because there's no 
 * point to doing that.
 * 2. Because of observation 1,
 * each possible decision must have
 * an alternative that doesn't 
 * go backwards.
 * 
 * Algorithm:
 * First, calculate shortest paths.
 * You can never pick the #1 option,
 * so always pick the #2 option in terms
 * of the distance.
 * 
 * Note: IDK if multi-source Dijkstra
 * works, but it should work. IDK.
*/

Compilation message

crocodile.cpp: In function 'int main()':
crocodile.cpp:43:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         for (auto [v, w] : adj[u]) {
      |                   ^
crocodile.cpp:57:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for (auto [v, w] : adj[u]) {
      |                   ^
crocodile.cpp:60:28: error: use of 'auto' in lambda parameter declaration only available with '-std=c++14' or '-std=gnu++14'
   60 |         sort(all(pos), [&](auto& x, auto& y) {
      |                            ^~~~
crocodile.cpp:60:37: error: use of 'auto' in lambda parameter declaration only available with '-std=c++14' or '-std=gnu++14'
   60 |         sort(all(pos), [&](auto& x, auto& y) {
      |                                     ^~~~
crocodile.cpp: In lambda function:
crocodile.cpp:61:21: error: invalid types 'int[int]' for array subscript
   61 |             return x[0] < y[0];
      |                     ^
crocodile.cpp:61:28: error: invalid types 'int[int]' for array subscript
   61 |             return x[0] < y[0];
      |                            ^
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 crocodile.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::vector<long long int>*, std::vector<std::vector<long long int> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = main()::<lambda(int&, int&)>]':
/usr/include/c++/10/bits/stl_algo.h:1846:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = main()::<lambda(int&, int&)>]'
crocodile.cpp:62:10:   required from here
/usr/include/c++/10/bits/predefined_ops.h:156:30: error: no match for call to '(main()::<lambda(int&, int&)>) (std::vector<long long int>&, std::vector<long long int>&)'
  156 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
crocodile.cpp:60:24: note: candidate: 'main()::<lambda(int&, int&)>'
   60 |         sort(all(pos), [&](auto& x, auto& y) {
      |                        ^
crocodile.cpp:60:24: note:   no known conversion for argument 1 from 'std::vector<long long int>' to 'int&'
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 crocodile.cpp:1:
/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::vector<long long int>; _Iterator = __gnu_cxx::__normal_iterator<std::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = main()::<lambda(int&, int&)>]':
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = main()::<lambda(int&, int&)>]'
crocodile.cpp:62:10:   required from here
/usr/include/c++/10/bits/predefined_ops.h:238:23: error: no match for call to '(main()::<lambda(int&, int&)>) (std::vector<long long int>&, std::vector<long long int>&)'
  238 |  { return bool(_M_comp(__val, *__it)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
crocodile.cpp:60:24: note: candidate: 'main()::<lambda(int&, int&)>'
   60 |         sort(all(pos), [&](auto& x, auto& y) {
      |                        ^
crocodile.cpp:60:24: note:   no known conversion for argument 1 from 'std::vector<long long int>' to 'int&'
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 crocodile.cpp:1:
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Value = std::vector<long long int>; _Compare = main()::<lambda(int&, int&)>]':
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Distance = long int; _Tp = std::vector<long long int>; _Compare = __gnu_cxx::__ops::_Iter_comp_val<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Distance = long int; _Tp = std::vector<long long int>; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int&, int&)> >]'
/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::vector<long long int>*, std::vector<std::vector<long long int> > >; _Compare = main()::<lambda(int&, int&)>]'
crocodile.cpp:62:10:   required from here
/usr/include/c++/10/bits/predefined_ops.h:194:23: error: no match for call to '(main()::<lambda(int&, int&)>) (std::vector<long long int>&, std::vector<long long int>&)'
  194 |  { return bool(_M_comp(*__it, __val)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
crocodile.cpp:60:24: note: candidate: 'main()::<lambda(int&, int&)>'
   60 |         sort(all(pos), [&](auto& x, auto& y) {
      |                        ^
crocodile.cpp:60:24: note:   no known conversion for argument 1 from 'std::vector<long long int>' to 'int&'