Submission #1282962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282962		vk3601h	Hard route (IZhO17_road)	C++20	100 / 100	673 ms	156388 KiB

road

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int node_num;
    cin >> node_num;

    vector<vector<int>> adj(node_num);
    for (int i = 0; i < node_num - 1; i++){
        int from, to;
        cin >> from >> to;
        from--, to--;
        adj[from].push_back(to);
        adj[to].push_back(from);
    }

    vector<int> max_length(node_num), path_count(node_num);
    function<void(int, int)> dfs = [&](int curr, int parent){
        max_length[curr] = 0;
        path_count[curr] = 1;
        for (int child : adj[curr]){
            if (child != parent){
                dfs(child, curr);
                if (max_length[curr] < max_length[child] + 1){
                    max_length[curr] = max_length[child] + 1;
                    path_count[curr] = path_count[child];
                }
                else if (max_length[curr] == max_length[child] + 1){
                    path_count[curr] += path_count[child];
                }
            }
        }
    };
    dfs(0, -1);

    long long max_hardness = 0, hardest_path_count = 1;
    function<void(int, int, long long, long long)> dfs2 = [&](int curr, int parent, long long parent_dist, long long parent_count){
        vector<array<long long, 2>> paths;
        if (curr > 0 || (int)adj[curr].size() == 1) paths.push_back({parent_dist, parent_count});
        for (int child : adj[curr]) if (child != parent) paths.push_back({max_length[child] + 1, path_count[child]});
        sort(paths.begin(), paths.end(), greater<array<long long, 2>>());

        if ((int)paths.size() >= 3){
            long long a = paths[0][0], b = paths[1][0], c = paths[2][0];
            long long curr_hardness = a * (b + c);
            long long curr_path_count = 0, ties = 0;
            for (const array<long long, 2> &path : paths) if (path[0] == c) ties += path[1];

            if (a != b && b != c){
                curr_path_count += paths[1][1] * ties;
            }
            else if (a == b && b == c){
                curr_path_count += ties * ties;
                for (const array<long long, 2> &path : paths) if (path[0] == c) curr_path_count -= path[1] * path[1];
                curr_path_count /= 2;
            }
            else if (a == b){
                curr_path_count += (paths[0][1] + paths[1][1]) * ties;
            }
            else if (b == c){
                curr_path_count += ties * ties;
                for (const array<long long, 2> &path : paths) if (path[0] == c) curr_path_count -= path[1] * path[1];
                curr_path_count /= 2;
            }

            if (max_hardness < curr_hardness){
                max_hardness = curr_hardness;
                hardest_path_count = curr_path_count;
            }
            else if (max_hardness == curr_hardness){
                hardest_path_count += curr_path_count;
            }
        }

        long long longest1 = 0, longest2 = 0, count1 = 0, count2 = 0;
        for (const array<long long, 2> &path : paths){
            if (path[0] + 1 > longest1){
                longest2 = longest1;
                count2 = count1;
                longest1 = path[0] + 1;
                count1 = path[1];
            }
            else if (path[0] + 1 == longest1){
                count1 += path[1];
            }
            else if (path[0] + 1 > longest2){
                longest2 = path[0] + 1;
                count2 = path[1];
            }
            else if (path[0] + 1 == longest2){
                count2 += path[1];
            }
        }

        for (int child : adj[curr]){
            if (child != parent){
                if (max_length[child] + 2 == longest1){
                    if (path_count[child] == count1) dfs2(child, curr, longest2, count2);
                    else dfs2(child, curr, longest1, count1 - path_count[child]);
                }
                else dfs2(child, curr, longest1, count1);
            }
        }
    };
    dfs2(0, -1, 0, 1);

    cout << max_hardness << " " << hardest_path_count;
    return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48