Submission #673185

#	Time	Username	Problem	Language	Result	Execution time	Memory
673185		finn__	Torrent (COI16_torrent)	C++17	0 / 100	2064 ms	26536 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));

    if (t.empty())
        return 0;

    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)
        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;
}

unsigned max_cover(unsigned s, vector<unsigned> const &path, unsigned t)
{
    unsigned a = 0, b = path.size() - 1;
    while (a < b)
    {
        unsigned mid = (a + b + 1) / 2;
        if (calc_dp(path[1], s, path[mid]) > t)
            b = mid - 1;
        else
            a = mid;
    }
    return a;
}

int main()
{
    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, UINT_MAX);
    vector<unsigned> path1, path2;
    find_path(s2, -1, s1, path1);
    find_path(s1, -1, s2, path2);
    reverse(path1.begin(), path1.end());
    reverse(path2.begin(), path2.end());

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

    unsigned a = 0, b = n;
    while (a < b)
    {
        unsigned t = (a + b) / 2;
        if (max_cover(s1, path1, t) >= path2.size() - max_cover(s2, path2, t) - 1)
            b = t;
        else
            a = t + 1;
    }

    cout << a << '\n';
}

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