Submission #934774

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934774	2024-02-28T01:05:11 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 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;
}
int 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) {
                num = ties * ties;
				for (auto [k, v] : opt) {
					if (k == opt[2].f) num -= v * v;
				}
				num /= 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;
				for (auto [k, v] : opt) {
					if (k == opt[2].f) num -= v * v;
				}
				num /= 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';
}

Compilation message

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