Submission #966316

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
966316	2024-04-19T17:17:01 Z	eysbutno	Hard route (IZhO17_road)	C++11	Compilation error	0 ms	0 KB

road

/**
 * Assume there is some hard route that goes from vertex
 * u to vertex v. Let the node that the path from u to v and the
 * furthest node from the hard route meet be node x. Use rerooting
 * DP to calculate the hardest route and the # of such hardest routes
 * for every node x.
 * 
 * Time Complexity: O(n log(n))
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n; 
    cin >> n;
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int x, y; 
        cin >> x >> y;
        --x, --y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    vector<int> max_length(n), path_count(n);
    auto dfs = [&](int u, int p, auto&& dfs) -> void {
		/**
         * Calculates the longest path from vertex u,
         * and the number of such paths.
        */
        max_length[u] = 0;
        path_count[u] = 1;
        for (int v : adj[u]) if (v != p) {
            dfs(v, u, dfs);
            if (max_length[u] < max_length[v] + 1) {
                max_length[u] = max_length[v] + 1;
                path_count[u] = path_count[v];
            } else if (max_length[v] + 1 == max_length[u]) {
                path_count[u] += path_count[v];
            }
        }
    }; 
    dfs(0, -1, dfs);

    ll max_hardness = 0, hardest_path_count = 1;
    auto dfs2 = [&](int u, int p, ll parDist, ll parCnt, 
                    auto&& dfs2) -> void {
		/**
         * Performs the rerooting, to count the hardest
         * path and the # of such paths at this vertex.
        */
        vector<array<ll, 2>> paths; // {distance, count}
        if (u > 0 || (int) adj[u].size() == 1) {
            paths.push_back({parDist, parCnt});
        }
        for (int v : adj[u]) if (v != p) {
            paths.push_back({max_length[v] + 1, path_count[v]});
        }
        sort(paths.begin(), paths.end(), greater<>());
        if ((int) adj[u].size() >= 3) { // can form a nonzero hard route
            /**
             * Let the 3 longest path lengths be a, b, c, with a > b > c.
             * The optimal hard route "hardness" is a * (b + c).
            */
            ll a = paths[0][0], b = paths[1][0], c = paths[2][0];
            ll cur = a * (b + c), num = 0, ties = 0;
            for (auto [k, v] : paths) {
                if (k == c) ties += v;
            }

            if (a != b && b != c) {
                // case 1: all are distinct.
                num = paths[1][1] * ties;
            } else if (a == b && b == c) {
                // case 2: all are the same.
                num = ties * ties;
				for (auto [k, v] : paths) {
					if (k == a) num -= v * v;
				}
				num /= 2; // avoiding double counting
            } else if (a == b) {
                // case 3: first two are the same.
                num = (paths[0][1] + paths[1][1]) * ties;
            } else {
                // case 4: last two are the same.
               	num = ties * ties;
				for (auto [k, v] : paths) {
					if (k == c) num -= v * v;
				}
				num /= 2; // avoiding double counting
            }
            
            if (max_hardness < cur) {
                max_hardness = cur;
                hardest_path_count = num;
            } else if (max_hardness == cur) {
                hardest_path_count += num;
            }
        }
        // processing parent dist and parent count.
        ll longest1 = 0;
        ll longest2 = 0;
        ll count1 = 0;
        ll count2 = 0;
        for (auto [k, v] : paths) {
            if (k + 1 > longest1) {
                swap(longest1, longest2);
                swap(count1, count2);
                longest1 = k + 1, count1 = v;
            } else if (k + 1 == longest1) {
                count1 += v;
            } else if (k + 1 > longest2) {
                longest2 = k + 1, count2 = v;
            } else if (k + 1 == longest2) {
                count2 += v;
            }
        }
        for (int v : adj[u]) if (v != p) {
            // using the best parent hardness and parent count possible.
            if (max_length[v] + 2 == longest1) {
                (path_count[v] == count1) ? dfs2(v, u, longest2, count2, dfs2) :
                            	            dfs2(v, u, longest1, count1 - path_count[v], dfs2);
            } else {
                dfs2(v, u, longest1, count1, dfs2);
            }
        }
    }; dfs2(0, -1, 0, 1, dfs2);
    cout << max_hardness << ' ' << hardest_path_count << '\n';
}

Compilation message

road.cpp: In function 'int main()':
road.cpp:27:34: error: use of 'auto' in lambda parameter declaration only available with '-std=c++14' or '-std=gnu++14'
   27 |     auto dfs = [&](int u, int p, auto&& dfs) -> void {
      |                                  ^~~~
road.cpp: In lambda function:
road.cpp:35:26: error: expression cannot be used as a function
   35 |             dfs(v, u, dfs);
      |                          ^
road.cpp: In function 'int main()':
road.cpp:44:19: error: no match for call to '(main()::<lambda(int, int, int&&)>) (int, int, main()::<lambda(int, int, int&&)>&)'
   44 |     dfs(0, -1, dfs);
      |                   ^
road.cpp:27:16: note: candidate: 'main()::<lambda(int, int, int&&)>'
   27 |     auto dfs = [&](int u, int p, auto&& dfs) -> void {
      |                ^
road.cpp:27:16: note:   no known conversion for argument 3 from 'main()::<lambda(int, int, int&&)>' to 'int&&'
road.cpp:48:21: error: use of 'auto' in lambda parameter declaration only available with '-std=c++14' or '-std=gnu++14'
   48 |                     auto&& dfs2) -> void {
      |                     ^~~~
road.cpp: In lambda function:
road.cpp:60:50: error: wrong number of template arguments (0, should be 1)
   60 |         sort(paths.begin(), paths.end(), greater<>());
      |                                                  ^
In file included from /usr/include/c++/10/string:48,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 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 road.cpp:10:
/usr/include/c++/10/bits/stl_function.h:371:12: note: provided for 'template<class _Tp> struct std::greater'
  371 |     struct greater : public binary_function<_Tp, _Tp, bool>
      |            ^~~~~~~
road.cpp:68:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |             for (auto [k, v] : paths) {
      |                       ^
road.cpp:78:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |     for (auto [k, v] : paths) {
      |               ^
road.cpp:88:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     for (auto [k, v] : paths) {
      |               ^
road.cpp:106:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |         for (auto [k, v] : paths) {
      |                   ^
road.cpp:122:78: error: expression cannot be used as a function
  122 |                 (path_count[v] == count1) ? dfs2(v, u, longest2, count2, dfs2) :
      |                                                                              ^
road.cpp:123:91: error: expression cannot be used as a function
  123 |                                          dfs2(v, u, longest1, count1 - path_count[v], dfs2);
      |                                                                                           ^
road.cpp:125:50: error: expression cannot be used as a function
  125 |                 dfs2(v, u, longest1, count1, dfs2);
      |                                                  ^
road.cpp: In function 'int main()':
road.cpp:128:30: error: no match for call to '(main()::<lambda(int, int, ll, ll, int&&)>) (int, int, int, int, main()::<lambda(int, int, ll, ll, int&&)>&)'
  128 |     }; dfs2(0, -1, 0, 1, dfs2);
      |                              ^
road.cpp:47:17: note: candidate: 'main()::<lambda(int, int, ll, ll, int&&)>'
   47 |     auto dfs2 = [&](int u, int p, ll parDist, ll parCnt,
      |                 ^
road.cpp:47:17: note:   no known conversion for argument 5 from 'main()::<lambda(int, int, ll, ll, int&&)>' to 'int&&'