Submission #673451

#	Time	Username	Problem	Language	Result	Execution time	Memory
673451		finn__	Torrent (COI16_torrent)	C++17	0 / 100	2077 ms	22548 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)
        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[0], s, path[mid]) > t)
            b = mid - 1;
        else
            a = mid;
    }
    return a;
}

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> path1, path2;
    find_path(s2, -1, s1, path1);
    find_path(s1, -1, s2, path2);

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

    vector<unsigned> x, y;
    for (unsigned v : g[s1])
        if (v != path1[0])
            x.push_back(calc_dp(v, s1));
    for (unsigned v : g[s2])
        if (v != path2[0])
            y.push_back(calc_dp(v, s2));
    sort(x.begin(), x.end(), greater<unsigned>());
    sort(y.begin(), y.end(), greater<unsigned>());

    unsigned a = 0, b = n;
    while (a < b)
    {
        unsigned t = (a + b) / 2;
        unsigned d1 = 0, d2 = 0;
        bool possible = 1;

        for (size_t i = 0; i < x.size() && possible; i++)
        {
            if (t < x[i] + i + 1 + (d1 != UINT_MAX))
                possible = 0;
            if (t <= x[i] && (!i || t >= x[i + 1]))
                d1 = i + 1;
        }

        for (size_t i = 0; i < y.size() && possible; i++)
        {
            if (t < y[i] + i + 1 + (d2 != UINT_MAX))
                possible = 0;
            if (t <= y[i] && (!i || t >= y[i + 1]))
                d2 = i + 1;
        }

        if (possible && max_cover(s1, path1, t - d1) >= path2.size() - max_cover(s2, path2, t - d2) - 1)
            b = t;
        else
            a = t + 1;
    }

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

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