Submission #94225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
94225	2019-01-16T22:29:20 Z	arknave	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

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

#define all(x) begin(x), end(x)

using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;

void dfs_sz(const vector<vector<pii>>& tree, vi& vis, vi& size, int u, int p = -1) {
    size[u] = 1;
    for (auto& e : tree[u]) {
        int v = e.first;
        if (v == p or vis[v])
            continue;
        dfs_sz(tree, vis, size, v, u);
        size[u] += size[v];
    }
}

int find_center(const vector<vector<pii>>& tree, vi& vis, vi& size, int tot, int u, int p = -1) {
    for (auto& e : tree[u]) {
        int v = e.first;
        if (v == p or vis[v]) 
            continue;
        if (2 * size[v] >= tot)
            return find_center(tree, vis, size, tot, v, u);
    }

    return u;
}

template <typename F>
void centroid(F& f, const vector<vector<pii>>& tree, vi& vis, vi& size, int u, int p = -1) {
    dfs_sz(tree, vis, size, u, p);
    int c = find_center(tree, vis, size, size[u], u, p);
    // do some shit here
    f(c);

    vis[u] = true;
    for (auto& e : tree[u]) {
        int v = e.first;
        if (v != p and !vis[v]) {
            centroid(f, tree, vis, size, v, u);
        }
    }
}

void dfs_path(const vector<vector<pii>>& tree, const vi& vis, int u, int p, ll path_len, int edges, map<ll, int>& m) {
    auto it = m.find(path_len);
    if (it == end(m) or it->second > edges) {
        m[path_len] = edges;
    }

    for (auto& e : tree[u]) {
        int v, w;
        tie(v, w) = e;
        if (vis[v] or v == p)
            continue;
        dfs_path(tree, vis, v, u, path_len + w, edges + 1, m);
    }
}

int solve(const vector<vector<pii>>& tree, int k) {
    int n = tree.size();
    vi vis(n, 0);

    constexpr int INF = 1e9 + 7;
    int ans = INF;
    auto f = [&](int u) {
        // one more dfs
        // path length -> shortest leg with that length
        // add then merge maps
        map<ll, int> left, right;
        left[0] = 0;
        for (auto& e : tree[u]) {
            int v, w;
            tie(v, w) = e;
            if (vis[v]) {
                continue;
            }

            right.clear();
            dfs_path(tree, vis, v, -1, w, 1, right);
            for (auto& p : right) {
                int path_len = p.first;
                int edges = p.second;
                auto it = left.find(k - path_len);
                if (it != end(left)) {
                    ans = min(ans, edges + it->second);
                }
            }

            left.insert(all(right));
        }
    };

    vi size(n, 0);
    centroid(f, tree, vis, size, 0, -1);

    return ans == INF ? -1 : ans;
}

int best_path(int n, int k, int h[][2], int l[]) {
    // create the tree
    vector<vector<pii>> tree(n);
    for (int i = 0; i < n - 1; ++i) {
        int u = h[i][0];
        int v = h[i][1];
        int w = l[i];

        tree[u].emplace_back(v, w);
        tree[v].emplace_back(u, w);
    }

    return solve(tree, k);
}

Compilation message

race.cpp:49:77: error: 'll' has not been declared
 void dfs_path(const vector<vector<pii>>& tree, const vi& vis, int u, int p, ll path_len, int edges, map<ll, int>& m) {
                                                                             ^~
race.cpp:49:105: error: 'll' was not declared in this scope
 void dfs_path(const vector<vector<pii>>& tree, const vi& vis, int u, int p, ll path_len, int edges, map<ll, int>& m) {
                                                                                                         ^~
race.cpp:49:105: note: suggested alternative: 'all'
 void dfs_path(const vector<vector<pii>>& tree, const vi& vis, int u, int p, ll path_len, int edges, map<ll, int>& m) {
                                                                                                         ^~
                                                                                                         all
race.cpp:49:112: error: template argument 1 is invalid
 void dfs_path(const vector<vector<pii>>& tree, const vi& vis, int u, int p, ll path_len, int edges, map<ll, int>& m) {
                                                                                                                ^
race.cpp:49:112: error: template argument 3 is invalid
race.cpp:49:112: error: template argument 4 is invalid
race.cpp: In function 'void dfs_path(const std::vector<std::vector<std::pair<int, int> > >&, const vi&, int, int, int, int, int&)':
race.cpp:50:17: error: request for member 'find' in 'm', which is of non-class type 'int'
     auto it = m.find(path_len);
                 ^~~~
race.cpp:51:20: error: no matching function for call to 'end(int&)'
     if (it == end(m) or it->second > edges) {
                    ^
In file included from /usr/include/c++/7/bits/range_access.h:36:0,
                 from /usr/include/c++/7/string:51,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/initializer_list:99:5: note: candidate: template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)
     end(initializer_list<_Tp> __ils) noexcept
     ^~~
/usr/include/c++/7/initializer_list:99:5: note:   template argument deduction/substitution failed:
race.cpp:51:20: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
     if (it == end(m) or it->second > edges) {
                    ^
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:68:5: note: candidate: template<class _Container> decltype (__cont.end()) std::end(_Container&)
     end(_Container& __cont) -> decltype(__cont.end())
     ^~~
/usr/include/c++/7/bits/range_access.h:68:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(_Container&) [with _Container = int]':
race.cpp:51:20:   required from here
/usr/include/c++/7/bits/range_access.h:68:48: error: request for member 'end' in '__cont', which is of non-class type 'int'
     end(_Container& __cont) -> decltype(__cont.end())
                                         ~~~~~~~^~~
/usr/include/c++/7/bits/range_access.h:78:5: note: candidate: template<class _Container> decltype (__cont.end()) std::end(const _Container&)
     end(const _Container& __cont) -> decltype(__cont.end())
     ^~~
/usr/include/c++/7/bits/range_access.h:78:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(const _Container&) [with _Container = int]':
race.cpp:51:20:   required from here
/usr/include/c++/7/bits/range_access.h:78:54: error: request for member 'end' in '__cont', which is of non-class type 'const int'
     end(const _Container& __cont) -> decltype(__cont.end())
                                               ~~~~~~~^~~
/usr/include/c++/7/bits/range_access.h:97:5: note: candidate: template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])
     end(_Tp (&__arr)[_Nm])
     ^~~
/usr/include/c++/7/bits/range_access.h:97:5: note:   template argument deduction/substitution failed:
race.cpp:51:20: note:   mismatched types '_Tp [_Nm]' and 'int'
     if (it == end(m) or it->second > edges) {
                    ^
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from race.cpp:2:
/usr/include/c++/7/valarray:1221:5: note: candidate: template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)
     end(valarray<_Tp>& __va)
     ^~~
/usr/include/c++/7/valarray:1221:5: note:   template argument deduction/substitution failed:
race.cpp:51:20: note:   mismatched types 'std::valarray<_Tp>' and 'int'
     if (it == end(m) or it->second > edges) {
                    ^
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from race.cpp:2:
/usr/include/c++/7/valarray:1231:5: note: candidate: template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)
     end(const valarray<_Tp>& __va)
     ^~~
/usr/include/c++/7/valarray:1231:5: note:   template argument deduction/substitution failed:
race.cpp:51:20: note:   mismatched types 'const std::valarray<_Tp>' and 'int'
     if (it == end(m) or it->second > edges) {
                    ^
race.cpp:52:19: error: invalid types 'int[int]' for array subscript
         m[path_len] = edges;
                   ^
race.cpp: In lambda function:
race.cpp:74:13: error: 'll' was not declared in this scope
         map<ll, int> left, right;
             ^~
race.cpp:74:13: note: suggested alternative: 'all'
         map<ll, int> left, right;
             ^~
             all
race.cpp:74:20: error: template argument 1 is invalid
         map<ll, int> left, right;
                    ^
race.cpp:74:20: error: template argument 3 is invalid
race.cpp:74:20: error: template argument 4 is invalid
race.cpp:75:15: error: invalid types 'int[int]' for array subscript
         left[0] = 0;
               ^
race.cpp:83:19: error: request for member 'clear' in 'right', which is of non-class type 'int'
             right.clear();
                   ^~~~~
race.cpp:85:28: error: 'begin' was not declared in this scope
             for (auto& p : right) {
                            ^~~~~
race.cpp:85:28: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from race.cpp:2:
/usr/include/c++/7/valarray:1211:5: note:   'std::begin'
     begin(const valarray<_Tp>& __va)
     ^~~~~
/usr/include/c++/7/valarray:1211:5: note:   'std::begin'
race.cpp:85:28: error: 'end' was not declared in this scope
             for (auto& p : right) {
                            ^~~~~
race.cpp:85:28: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from race.cpp:2:
/usr/include/c++/7/valarray:1231:5: note:   'std::end'
     end(const valarray<_Tp>& __va)
     ^~~
/usr/include/c++/7/valarray:1231:5: note:   'std::end'
race.cpp:88:32: error: request for member 'find' in 'left', which is of non-class type 'int'
                 auto it = left.find(k - path_len);
                                ^~~~
race.cpp:94:18: error: request for member 'insert' in 'left', which is of non-class type 'int'
             left.insert(all(right));
                  ^~~~~~
race.cpp:4:23: error: no matching function for call to 'begin(int&)'
 #define all(x) begin(x), end(x)
                       ^
race.cpp:94:25: note: in expansion of macro 'all'
             left.insert(all(right));
                         ^~~
In file included from /usr/include/c++/7/bits/range_access.h:36:0,
                 from /usr/include/c++/7/string:51,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/initializer_list:89:5: note: candidate: template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)
     begin(initializer_list<_Tp> __ils) noexcept
     ^~~~~
/usr/include/c++/7/initializer_list:89:5: note:   template argument deduction/substitution failed:
race.cpp:4:23: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
 #define all(x) begin(x), end(x)
                       ^
race.cpp:94:25: note: in expansion of macro 'all'
             left.insert(all(right));
                         ^~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:48:5: note: candidate: template<class _Container> decltype (__cont.begin()) std::begin(_Container&)
     begin(_Container& __cont) -> decltype(__cont.begin())
     ^~~~~
/usr/include/c++/7/bits/range_access.h:48:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&) [with _Container = int]':
race.cpp:94:25:   required from here
/usr/include/c++/7/bits/range_access.h:48:50: error: request for member 'begin' in '__cont', which is of non-class type 'int'
     begin(_Container& __cont) -> decltype(__cont.begin())
                                           ~~~~~~~^~~~~
/usr/include/c++/7/bits/range_access.h:58:5: note: candidate: template<class _Container> decltype (__cont.begin()) std::begin(const _Container&)
     begin(const _Container& __cont) -> decltype(__cont.begin())
     ^~~~~
/usr/include/c++/7/bits/range_access.h:58:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(const _Container&) [with _Container = int]':
race.cpp:94:25:   required from here
/usr/include/c++/7/bits/range_access.h:58:56: error: request for member 'begin' in '__cont', which is of non-class type 'const int'
     begin(const _Container& __cont) -> decltype(__cont.begin())
                                                 ~~~~~~~^~~~~
/usr/include/c++/7/bits/range_access.h:87:5: note: candidate: template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])
     begin(_Tp (&__arr)[_Nm])
     ^~~~~
/usr/include/c++/7/bits/range_access.h:87:5: note:   template argument deduction/substitution failed:
race.cpp:4:23: note:   mismatched types '_Tp [_Nm]' and 'int'
 #define all(x) begin(x), end(x)
                       ^
race.cpp:94:25: note: in expansion of macro 'all'
             left.insert(all(right));
                         ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from race.cpp:2:
/usr/include/c++/7/valarray:1201:5: note: candidate: template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)
     begin(valarray<_Tp>& __va)
     ^~~~~
/usr/include/c++/7/valarray:1201:5: note:   template argument deduction/substitution failed:
race.cpp:4:23: note:   mismatched types 'std::valarray<_Tp>' and 'int'
 #define all(x) begin(x), end(x)
                       ^
race.cpp:94:25: note: in expansion of macro 'all'
             left.insert(all(right));
                         ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from race.cpp:2:
/usr/include/c++/7/valarray:1211:5: note: candidate: template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)
     begin(const valarray<_Tp>& __va)
     ^~~~~
/usr/include/c++/7/valarray:1211:5: note:   template argument deduction/substitution failed:
race.cpp:4:23: note:   mismatched types 'const std::valarray<_Tp>' and 'int'
 #define all(x) begin(x), end(x)
                       ^
race.cpp:94:25: note: in expansion of macro 'all'
             left.insert(all(right));
                         ^~~
race.cpp:4:31: error: no matching function for call to 'end(int&)'
 #define all(x) begin(x), end(x)
                               ^
race.cpp:94:25: note: in expansion of macro 'all'
             left.insert(all(right));
                         ^~~
In file included from /usr/include/c++/7/bits/range_access.h:36:0,
                 from /usr/include/c++/7/string:51,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/initializer_list:99:5: note: candidate: template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)
     end(initializer_list<_Tp> __ils) noexcept
     ^~~
/usr/include/c++/7/initializer_list:99:5: note:   template argument deduction/substitution failed:
race.cpp:4:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
 #define all(x) begin(x), end(x)
                               ^
race.cpp:94:25: note: in expansion of macro 'all'
             left.insert(all(right));
                         ^~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/bits/range_access.h:68:5: note: candidate: template<class _Container> decltype (__cont.end()) std::end(_Container&)
     end(_Container& __cont) -> decltype(__cont.end())
     ^~~
/usr/include/c++/7/bits/range_access.h:68:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(_Container&) [with _Container = int]':
race.cpp:94:25:   required from here
/usr/include/c++/7/bits/range_access.h:68:48: error: request for member 'end' in '__cont', which is of non-class type 'int'
     end(_Container& __cont) -> decltype(__cont.end())
                                         ~~~~~~~^~~
/usr/include/c++/7/bits/range_access.h:78:5: note: candidate: template<class _Container> decltype (__cont.end()) std::end(const _Container&)
     end(const _Container& __cont) -> decltype(__cont.end())
     ^~~
/usr/include/c++/7/bits/range_access.h:78:5: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(const _Container&) [with _Container = int]':
race.cpp:94:25:   required from here
/usr/include/c++/7/bits/range_access.h:78:54: error: request for member 'end' in '__cont', which is of non-class type 'const int'
     end(const _Container& __cont) -> decltype(__cont.end())
                                               ~~~~~~~^~~
/usr/include/c++/7/bits/range_access.h:97:5: note: candidate: template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])
     end(_Tp (&__arr)[_Nm])
     ^~~
/usr/include/c++/7/bits/range_access.h:97:5: note:   template argument deduction/substitution failed:
race.cpp:4:31: note:   mismatched types '_Tp [_Nm]' and 'int'
 #define all(x) begin(x), end(x)
                               ^
race.cpp:94:25: note: in expansion of macro 'all'
             left.insert(all(right));
                         ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from race.cpp:2:
/usr/include/c++/7/valarray:1221:5: note: candidate: template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)
     end(valarray<_Tp>& __va)
     ^~~
/usr/include/c++/7/valarray:1221:5: note:   template argument deduction/substitution failed:
race.cpp:4:31: note:   mismatched types 'std::valarray<_Tp>' and 'int'