Submission #1355442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355442		i_love_spring	Torrent (COI16_torrent)	C++20	Compilation error	0 ms	0 KiB

torrent

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long 
const int inf = 2e9;
#define int long long 

void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    --a, --b;
    vector<vector<int>> g(n);
    for (int i = 1; i < n;i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }


    vector<int> dpA(n, 0), parA(n, -1);
    
    function<void(int, int)> dfsA = [&](int u, int p) {
        vector<int> arr;
        for (int v : g[u]) {
            if (v == p)
                continue;
            dfsA(v, u);
            parA[v] = u;
            if (v != b) 
                arr.push_back(dpA[v]);
        }

        sort(arr.rbegin(), arr.rend());
        for (int i = 0; i < arr.size(); i++)
            dpA[u] = max(dpA[u], i + 1 + arr[i]);

    };

    dfsA(a, -1);
    

    vector<int> dpB(n, 0), parB(n, -1);
    
    function<void(int, int)> dfsB = [&](int u, int p) {
        vector<int> arr;
        for (int v : g[u]) {
            if (v == p)
                continue;
            dfsB(v, u);
            parB[v] = u;
            if (v != a) 
                arr.push_back(dpB[v]);
        }

        sort(arr.rbegin(), arr.rend());
        for (int i = 0; i < arr.size(); i++)
            dpB[u] = max(dpB[u], i + 1 + arr[i]);

    };

    dfsB(b, -1);

    vector<int> path;
    int cur = parB[a];
    while (cur != b) 
        path.push_back(cur), cur = parB[cur];
    
    reverse(path.begin(), path.end());

    auto f = [&](int x) {
        if (x >= path.size() | x < 0)
            return inf;
        auto tmpA = dpA;
        auto tmpB = dpB;
        x = path[x];
        int z = parA[x];
        while (z != -1) {
            vector<int> arr;
            for (int v : g[z]) {
                if (v == parA[z] || v == x) 
                    continue;
                arr.push_back(dpA[v]);
            }
            
            dpA[z] = 0;
            sort(arr.rbegin(), arr.rend());
            for (int i = 1; i <= arr.size(); i++)
                dpA[z] = max(dpA[z], i + arr[i - 1]);
            z = parA[z];
        }

        z = x;
        while (z != -1) {
            vector<int> arr;
            for (int v : g[z]) {
                if (v == parB[z] || v == parA[x]) 
                    continue;
                arr.push_back(dpB[v]);
            }


            dpB[z] = 0;
            sort(arr.rbegin(), arr.rend());
            for (int i = 1; i <= arr.size(); i++)
                dpB[z] = max(dpB[z], i + arr[i - 1]);
            z = parB[z];
        }
        int res = max(dpA[a], dpB[b]);
        dpA = tmpA;
        dpB = tmpB;
        return res;
    };    

    int ans = max(dpA[a], dpB[b]);
    // for (int i = 0; i < path.size();i++)
    //     ans = min(ans, f(i));
    int l = 0, r = path.size() - 1;
    while (l < r) {
        int m = (l + r) / 2;
        int x1 = f(m);
        int x2 = f(m + 1);
        ans = min({ans, x1, x2});
        if (x1 >= x2)
            l = m + 1;
        else 
            r = m;
    }

    ans = min({ans, f(l), f(r)});

    cout << ans << "\n";
}

int32_t main() { 

#ifdef Behruz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif 

    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    solve();

    return 0;
}

Compilation message (stderr)

torrent.cpp: In lambda function:
torrent.cpp:115:16: error: inconsistent types 'int' and 'long long int' deduced for lambda return type
  115 |         return res;
      |                ^~~
torrent.cpp: In function 'void solve()':
torrent.cpp:133:14: error: no matching function for call to 'min(<brace-enclosed initializer list>)'
  133 |     ans = min({ans, f(l), f(r)});
      |           ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from torrent.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
torrent.cpp:133:14: note:   candidate expects 2 arguments, 1 provided
  133 |     ans = min({ans, f(l), f(r)});
      |           ~~~^~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
torrent.cpp:133:14: note:   candidate expects 3 arguments, 1 provided
  133 |     ans = min({ans, f(l), f(r)});
      |           ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5775 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note:   template argument deduction/substitution failed:
torrent.cpp:133:14: note:   deduced conflicting types for parameter '_Tp' ('long long int' and 'int')
  133 |     ans = min({ans, f(l), f(r)});
      |           ~~~^~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note:   template argument deduction/substitution failed:
torrent.cpp:133:14: note:   deduced conflicting types for parameter '_Tp' ('long long int' and 'int')
  133 |     ans = min({ans, f(l), f(r)});
      |           ~~~^~~~~~~~~~~~~~~~~~~