제출 #639786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
639786		finn__	Torrent (COI16_torrent)	C++17	0 / 100	233 ms	23504 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--;

    if (n == 2)
    {
        cout << 0 << '\n';
        return 0;
    }

    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++)
    {
        x5 = min(x5, max(dp2[i], dp1[i + 1]) + 1);
    }

    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