Submission #947052

#	Time	Username	Problem	Language	Result	Execution time	Memory
947052		atom	Hard route (IZhO17_road)	C++17	19 / 100	2060 ms	12376 KiB

road

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 5e5 + 5;
int n;
vector <int> adj[N];
vector <int> path;
bool found;

void dfs(int a, int b, int p) {
    if (found) return;
    path.push_back(a);
    for (int v : adj[a]) {
        if (v == p) continue;
        dfs(v, b, a);
        if (v == b) {
            path.push_back(b);
            found = true;
            return;
        }
    }
    if (found) return;
    path.pop_back();
}
signed main() {
    cin.tie(0) -> sync_with_stdio(0);

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

    //sub1: O(n^3)
    vector <int> ter;
    for (int i = 1; i <= n; ++i)
        if ((int) adj[i].size() == 1)
            ter.push_back(i);

    int ans = 0, cnt = 0;
    for (int i = 0; i < (int) ter.size(); ++i) {
        for (int j = i + 1; j < (int) ter.size(); ++j) {
            path.clear(); found = false;
            dfs(ter[i], ter[j], 0);

            vector <int> dis(n + 5, 1e9);
            queue <int> q;
            for (int x : path) {
                q.push(x);
                dis[x] = 0;
            }

            while (!q.empty()) {
                int x = q.front(); q.pop();
                for (int y : adj[x]) {
                    if (dis[y] > dis[x] + 1) {
                        dis[y] = dis[x] + 1;
                        q.push(y);
                    }
                }
            }

            int len = (int) path.size() - 1;
            int h = 0;
            for (int x = 1; x <= n; ++x)
                h = max(h, dis[x]);
            if (h == (int) (1e9)) h = 0;
            
            if (ans < h * len) {
                ans = h * len;
                cnt = 1;
            }
            else if (ans == h * len) {
                cnt++;
            }
        }
    }

    cout << ans << " " << cnt << "\n";

    return 0;
}

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