Submission #934772

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934772	2024-02-28T00:49:39 Z	eysbutno	Hard route (IZhO17_road)	C++11	Compilation error	0 ms	0 KB

road

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define int long long // NOOOO
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first 
#define s second 

template<class T> bool smin(T& a, T b) {
    return b < a ? a = b, 1 : 0;
}
template<class T> bool smax(T& a, T b) {
    return b > a ? a = b, 1 : 0;
}
int32_t main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n; cin >> n;
    vector adj(n, vector<int>());
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        adj[--x].push_back(--y);
        adj[y].push_back(x);
    }
    vector<int> d(n), c(n);
    auto dfs = [&](int u, int p, auto&& dfs) -> void {
        d[u] = 0, c[u] = 1;
        for (int v : adj[u]) if (v != p) {
            dfs(v, u, dfs);
            if (smax(d[u], d[v] + 1)) {
                c[u] = c[v];
            } else if (d[v] + 1 == d[u]) {
                c[u] += c[v];
            }
        }
    }; dfs(0, -1, dfs);
    ll hard = 0, cnt = 1;
    auto dfs2 = [&](int u, int p, int pd, int pc, 
                    auto&& dfs2) -> void {
        vector<pii> opt;
        if (u > 0 || sz(adj[u]) == 1) {
            opt.push_back({pd, pc});
        }
        for (int v : adj[u]) if (v != p) {
            opt.push_back({d[v] + 1, c[v]});
        }
        sort(all(opt), greater<>());
        if (sz(adj[u]) >= 3) { // can form nonzero path
            ll cur = opt[0].f * (opt[1].f + opt[2].f), 
               num = 0;
            int ties = 0; // equal to third element
            for (auto [k, v] : opt) {
                if (k == opt[2].f) ties += v;
            }
            // case 1: all are distinct
            if (opt[0].f != opt[1].f &&
                opt[1].f != opt[2].f) {
                // num = opt[0].s * opt[1].s * ties;
                num = opt[1].s * ties;
            }
            // case 2: all are the same
            else if (opt[0].f == opt[1].f &&
                opt[1].f == opt[2].f) {
                // n choose 2, in this case
                num = ties * (ties - 1) / 2;
            }
            // case 3: first two are the same
            else if (opt[0].f == opt[1].f) {
                num = (opt[0].s + opt[1].s) * ties;
            }
            // case 4: last two are the same
            else {
                num = ties * (ties - 1) / 2;
            }
            if (smax(hard, cur)) {
                cnt = num;
            } else if (hard == cur) {
                cnt += num;
            }
        }
        // processing parent dist & parent count
        int l1 = 0, l2 = 0, cnt1 = 0, cnt2 = 0;
        for (auto [k, v] : opt) {
            // all paths will increase by len 1
            if (k + 1 > l1) {
                swap(l1, l2), swap(cnt1, cnt2);
                l1 = k + 1, cnt1 = v;
            } else if (k + 1 == l1) {
                cnt1 += v;
            } else if (k + 1 > l2) {
                l2 = k + 1, cnt2 = v;
            } else if (k + 1 == l2) {
                cnt2 += v;
            }
        }
        for (int v : adj[u]) if (v != p) {
            if (d[v] + 2 == l1) {
                (c[v] == cnt1) ? dfs2(v, u, l2, cnt2, dfs2) :
                            	 dfs2(v, u, l1, cnt1 - c[v], dfs2);
            } else {
                dfs2(v, u, l1, cnt1, dfs2);
            }
        }
    }; dfs2(0, -1, 0, 1, dfs2);
    cout << hard << ' ' << cnt << '\n';
}
/**
 * TASK: Hard Route (IZhO).
 * Terminals are (obviously) leaves.
 * Probably will consider all paths 
 * from a given LCA (from which the
 * longest distance lies on).
 * 
 * So, DFS over every root x, where
 * the endpoints and farthest nodes
 * can be chosen. NOTE THAT THE PATH
 * WILL BE THE TWO SHORTER DISTANCES!
 * (Note that using this information,
 * you can prove that no (u, v) pair
 * will be double counted.)
*/

Compilation message

road.cpp: In function 'int32_t main()':
road.cpp:20:12: error: missing template arguments before 'adj'
   20 |     vector adj(n, vector<int>());
      |            ^~~
road.cpp:23:9: error: 'adj' was not declared in this scope
   23 |         adj[--x].push_back(--y);
      |         ^~~
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:29:22: error: 'adj' was not declared in this scope
   29 |         for (int v : adj[u]) if (v != p) {
      |                      ^~~
road.cpp:30:26: error: expression cannot be used as a function
   30 |             dfs(v, u, dfs);
      |                          ^
road.cpp: In function 'int32_t main()':
road.cpp:37:22: error: no match for call to '(main()::<lambda(long long int, long long int, int&&)>) (int, int, main()::<lambda(long long int, long long int, int&&)>&)'
   37 |     }; dfs(0, -1, dfs);
      |                      ^
road.cpp:27:16: note: candidate: 'main()::<lambda(long long int, long long 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(long long int, long long int, int&&)>' to 'int&&'
road.cpp:40:21: error: use of 'auto' in lambda parameter declaration only available with '-std=c++14' or '-std=gnu++14'
   40 |                     auto&& dfs2) -> void {
      |                     ^~~~
road.cpp: In lambda function:
road.cpp:42:25: error: 'adj' was not declared in this scope
   42 |         if (u > 0 || sz(adj[u]) == 1) {
      |                         ^~~
road.cpp:7:22: note: in definition of macro 'sz'
    7 | #define sz(x) (int) (x).size()
      |                      ^
road.cpp:45:22: error: 'adj' was not declared in this scope
   45 |         for (int v : adj[u]) if (v != p) {
      |                      ^~~
road.cpp:48:32: error: wrong number of template arguments (0, should be 1)
   48 |         sort(all(opt), 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:1:
/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:49:16: error: 'adj' was not declared in this scope
   49 |         if (sz(adj[u]) >= 3) { // can form nonzero path
      |                ^~~
road.cpp:7:22: note: in definition of macro 'sz'
    7 | #define sz(x) (int) (x).size()
      |                      ^
road.cpp:53:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |             for (auto [k, v] : opt) {
      |                       ^
road.cpp:84:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |         for (auto [k, v] : opt) {
      |                   ^
road.cpp:97:22: error: 'adj' was not declared in this scope
   97 |         for (int v : adj[u]) if (v != p) {
      |                      ^~~
road.cpp:99:59: error: expression cannot be used as a function
   99 |                 (c[v] == cnt1) ? dfs2(v, u, l2, cnt2, dfs2) :
      |                                                           ^
road.cpp:100:63: error: expression cannot be used as a function
  100 |                               dfs2(v, u, l1, cnt1 - c[v], dfs2);
      |                                                               ^
road.cpp:102:42: error: expression cannot be used as a function
  102 |                 dfs2(v, u, l1, cnt1, dfs2);
      |                                          ^
road.cpp: In function 'int32_t main()':
road.cpp:105:30: error: no match for call to '(main()::<lambda(long long int, long long int, long long int, long long int, int&&)>) (int, int, int, int, main()::<lambda(long long int, long long int, long long int, long long int, int&&)>&)'
  105 |     }; dfs2(0, -1, 0, 1, dfs2);
      |                              ^
road.cpp:39:17: note: candidate: 'main()::<lambda(long long int, long long int, long long int, long long int, int&&)>'
   39 |     auto dfs2 = [&](int u, int p, int pd, int pc,
      |                 ^
road.cpp:39:17: note:   no known conversion for argument 5 from 'main()::<lambda(long long int, long long int, long long int, long long int, int&&)>' to 'int&&'