Submission #1183976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183976		al_reem_2010	Hard route (IZhO17_road)	C++20	19 / 100	16 ms	840 KiB

road

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

#define int long long
#define pb push_back
#define si size()
#define all(a) a.begin(),a.end()
#define applejuice ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

const int inf = 1e18;
vector<int> l[107]; // adjacency list
vector<int> a;      // terminals
vector<int> ans;    // hardnesses
vector<vector<int>> mm; // paths between terminals
int dis[107], fdis[107];
int r = 0;

bool dfs(int i, int j, int p) {
    for (int k = 0; k < l[i].si; k++) {
        if (l[i][k] == p) continue;
        if (l[i][k] == j) {
            mm[r].pb(l[i][k]);
            mm[r].pb(i);
            return true;
        }
        if (dfs(l[i][k], j, i)) {
            mm[r].pb(i);
            return true;
        }
    }
    return false;
}

void dfs1(int k, int p, int m) {
    dis[k] = m;
    for (int i = 0; i < l[k].si; i++) {
        int to = l[k][i];
        if (to == p || to == mm[r][0] || to == mm[r].back()) continue;
        dfs1(to, k, m + 1);
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        l[u].pb(v);
        l[v].pb(u);
    }

    for (int i = 1; i <= n; i++) {
        if (l[i].si == 1) a.pb(i); // terminals
    }

    for (int i = 0; i < a.si; i++) {
        for (int j = i + 1; j < a.si; j++) {
            mm.pb({}); // push new path container
            r = mm.si - 1;
            dfs(a[i], a[j], -1);
            if (mm[r].empty()) continue;

            reverse(all(mm[r])); // ترتيب المسار
            fill(dis, dis + 107, -inf);
            fill(fdis, fdis + 107, inf);

            for (int k = 1; k < mm[r].si - 1; k++) {
                dfs1(mm[r][k], -1, 0);
                for (int h = 1; h <= n; h++) {
                    fdis[h] = min(fdis[h], dis[h]);
                }
            }

            int anss = -inf;
            for (int k = 1; k <= n; k++) {
                anss = max(anss, fdis[k]);
            }

            if (a.si == 2) anss = 0;
            ans.pb((mm[r].si - 1) * anss);
        }
    }

    int mx = *max_element(all(ans)), cnt = 0;
    for (auto x : ans) cnt += (x == mx);
    cout << mx << " " << cnt << "\n";
}

signed main() {
    applejuice;
    solve();
}

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