Submission #673460

#	Time	Username	Problem	Language	Result	Execution time	Memory
673460		finn__	Torrent (COI16_torrent)	C++17	100 / 100	440 ms	28252 KiB

torrent

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

vector<vector<unsigned>> g;
vector<unsigned> dp;

unsigned calc_dp(unsigned u, unsigned p = -1, unsigned f = -1)
{
    dp[u] = 0;
    vector<unsigned> t;

    for (unsigned v : g[u])
        if (v != p && v != f)
            t.push_back(calc_dp(v, u, f));

    sort(t.begin(), t.end(), greater<unsigned>());
    for (unsigned i = 0; i < t.size(); i++)
        dp[u] = max(dp[u], t[i] + i + 1);
    return dp[u];
}

bool find_path(unsigned u, unsigned p, unsigned t, vector<unsigned> &path)
{
    if (u == t)
    {
        path.push_back(u);
        return 1;
    }
    for (unsigned v : g[u])
        if (v != p)
            if (find_path(v, u, t, path))
            {
                path.push_back(u);
                return 1;
            }

    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n;
    unsigned s1, s2;
    cin >> n >> s1 >> s2;
    s1--;
    s2--;

    g = vector<vector<unsigned>>(n);
    for (size_t i = 0; i < n - 1; i++)
    {
        unsigned u, v;
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }

    dp = vector<unsigned>(n);
    vector<unsigned> path;
    find_path(s2, -1, s1, path);

    if (path.size() == 2)
    {
        cout << max(calc_dp(s1, s2), calc_dp(s2, s1)) << '\n';
        return 0;
    }

    unsigned a = 0, b = path.size() - 2, min_time = UINT_MAX;

    while (a < b)
    {
        unsigned mid = (a + b) / 2;
        unsigned x = calc_dp(s1, -1, path[mid + 1]),
                 y = calc_dp(s2, -1, path[mid]);

        min_time = min(min_time, max(x, y));
        if (x < y)
            a = mid + 1;
        else
            b = mid;
    }

    if (a)
        min_time = min(min_time, max(calc_dp(s1, -1, path[a]), calc_dp(s2, -1, path[a - 1])));

    cout << min_time << '\n';
}

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69