Submission #639780

#	Time	Username	Problem	Language	Result	Execution time	Memory
639780		finn__	Torrent (COI16_torrent)	C++17	0 / 100	236 ms	23472 KiB

torrent

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

vector<vector<unsigned>> g;

unsigned solve_for_one(unsigned u, unsigned p, vector<unsigned> &dp, unsigned w = -1)
{
    if (g[u].size() == 1 && g[u][0] == p)
        return 0;

    vector<unsigned> children_times;

    for (unsigned v : g[u])
        if (v != p && v != w)
            children_times.push_back(solve_for_one(v, u, dp, w));

    sort(children_times.begin(), children_times.end());
    unsigned total = 0, i = 1;
    for (auto it = children_times.rbegin(); it != children_times.rend(); it++)
    {
        total = max(*it + i, total);
        i++;
    }

    dp[u] = total;
    return total;
}

bool find_path(unsigned u, unsigned p, unsigned v, vector<unsigned> &path)
{
    path.push_back(u);

    if (u == v)
        return 1;

    for (unsigned x : g[u])
        if (x != p)
            if (find_path(x, u, v, path))
                return 1;

    path.pop_back();
    return 0;
}

int main()
{
    size_t n;
    unsigned a, b;
    cin >> n >> a >> b;
    a--;
    b--;

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

    vector<unsigned> p;
    find_path(a, -1, b, p);
    unsigned l = p.size() - 1;

    vector<unsigned> dp1(n), dp2(n);
    unsigned x1 = solve_for_one(a, p[1], dp1),
             x2 = solve_for_one(b, p[p.size() - 2], dp1),
             x3 = solve_for_one(p[1], a, dp1, b) + 1,
             x4 = solve_for_one(p[p.size() - 2], b, dp2, a) + 1;

    unsigned x5 = UINT_MAX;

    for (unsigned i = 0; i < l; i++)
    {
        vector<unsigned> xtime, ytime;
        unsigned x = p[i], y = p[i + 1];

        for (unsigned v : g[x])
            if (v != y && (!i || v != p[i - 1]))
                xtime.push_back(dp1[v]);

        for (unsigned v : g[y])
            if (v != x && (i == l - 1 || v != p[i + 1]))
                ytime.push_back(dp2[v]);

        sort(xtime.begin(), xtime.end());
        sort(ytime.begin(), ytime.end());

        unsigned xv1 = 0, yv2 = 0;

        unsigned j = 1;
        for (auto it = xtime.rbegin(); it != xtime.rend(); it++)
        {
            xv1 = max(*it + j, xv1);
            j++;
        }
        j = 1;
        for (auto it = ytime.rbegin(); it != ytime.rend(); it++)
        {
            yv2 = max(*it + j, yv2);
            j++;
        }

        x5 = min(x5, max(xv1 + i, yv2 + l - i));
    }

    if (p.size() == 2)
        x3 = x4 = x5 = 0;

    unsigned min_cost = UINT_MAX;

    min_cost = min(min_cost, max(x1, max(x2, x5 + 1)));
    min_cost = min(min_cost, max(x1 + 1, max(x2 + 1, x5)));
    min_cost = min(min_cost, max(x1, max(x2 + 1, x4)));
    min_cost = min(min_cost, max(x1, max(x2, x4 + 1)));
    min_cost = min(min_cost, max(x2, max(x1 + 1, x3)));
    min_cost = min(min_cost, max(x2, max(x1, x3 + 1)));

    cout << min_cost << '\n';
}

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