Submission #1191563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191563		tin_le	Hard route (IZhO17_road)	C++20	19 / 100	2101 ms	196868 KiB

road

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

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

    int N;
    cin >> N;
    vector<vector<int>> adj(N+1);
    for(int i = 0, u, v; i < N-1; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> leaves;
    for(int i = 1; i <= N; i++)
        if(adj[i].size() == 1)
            leaves.push_back(i);

    // dist[a][b] = distance from a to b
    // parent[a][v] = predecessor of v in BFS tree rooted at a
    vector<vector<int>> dist(N+1, vector<int>(N+1));
    vector<vector<int>> parent(N+1, vector<int>(N+1, -1));

    // Precompute all-pairs distances + parents
    for(int a = 1; a <= N; a++){
        vector<bool> vis(N+1);
        queue<int> q;
        q.push(a);
        vis[a] = true;
        dist[a][a] = 0;
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(int v: adj[u]){
                if(!vis[v]){
                    vis[v] = true;
                    dist[a][v] = dist[a][u] + 1;
                    parent[a][v] = u;
                    q.push(v);
                }
            }
        }
    }

    long long bestH = 0;
    int countH = 0;
    int L = leaves.size();

    // Enumerate every leaf–leaf pair
    for(int i = 0; i < L; i++){
        for(int j = i+1; j < L; j++){
            int A = leaves[i], B = leaves[j];
            int d = dist[A][B];

            // Reconstruct path A→…→B
            vector<int> path;
            for(int x = B; x != -1; x = parent[A][x]){
                path.push_back(x);
                if(x == A) break;
            }

            // For each city v, find min dist to any node on the path
            long long H = 0;
            for(int v = 1; v <= N; v++){
                int md = N;
                for(int p: path)
                    md = min(md, dist[v][p]);
                H = max(H, (long long)md);
            }

            long long hard = d * H;
            if(hard > bestH){
                bestH = hard;
                countH = 1;
            } else if(hard == bestH){
                countH++;
            }
        }
    }

    cout << bestH << " " << countH << "\n";
    return 0;
}

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