Submission #758168

#	Time	Username	Problem	Language	Result	Execution time	Memory
758168		vjudge1	Hard route (IZhO17_road)	C++17	0 / 100	9 ms	12116 KiB

road

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

#define int long long

const int mxN = 5e5 + 7;

int mx, d[mxN], ans, cnt, og;
vector<int> g[mxN], a, b;
set<pair<int,int>> check;

void findFirst(int u, int par, int dist) {
    if (dist > mx) {
        mx = dist;
        a.clear();
        a.push_back(u);
    }
    else {
        a.push_back(u);
    }

    for (auto v : g[u]) {
        if (v != par) {
            findFirst(v, u, dist + 1);
        }
    }
}

void findSecond(int u, int par, int dist) {
    d[u] = dist;
    if (dist > mx) {
        mx = dist;
        b.clear();
        b.push_back(u);
    }
    else if (dist == mx) {
        b.push_back(u);
    }

    for (auto v : g[u]) {
        if (v != par) {
            findSecond(v, u, dist + 1);
        }
    }
}
    
void dfs(int u, int par, int dist, int cur) {
    cur = min(cur, d[u]);
    if (g[u].size() == 1 && par) {
        if (dist * cur > ans) {
            ans = dist * cur;
            check.clear();
            check.insert({og, u});
            check.insert({u, og});
        }
        else if (dist * cur == ans) {
            ++cnt;
            check.insert({og, u});
            check.insert({u, og});
        }
    }

    for (auto v : g[u]) {
        if (v != par) {
            dfs(v, u, dist + 1, cur);
        } 
    }
}

int32_t main() {
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    mx = -1;
    findFirst(1, 0, 0);
    a.push_back(1);
    
    ans = -1;
    for (auto u : a) {
        mx = -1;
        findSecond(u, 0, 0);

        for (auto v : b) {
            og = v;
            dfs(v, 0, 0, d[v]);
        }
        b.clear();
    }
    cout << ans << ' ' << check.size() / 2 << "\n";
}

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