제출 #1227392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227392		borisAngelov	Torrent (COI16_torrent)	C++20	100 / 100	224 ms	23752 KiB

torrent

#include <bits/stdc++.h>

using namespace std;

const int maxn = 300005;

int n, a, b;
vector<int> g[maxn];
int parent[maxn];

void dfsInit(int node, int par)
{
    parent[node] = par;

    for (auto to : g[node])
    {
        if (to != par)
        {
            dfsInit(to, node);
        }
    }
}

vector<int> path;
bool marked[maxn];

int dfs(int node, int par, int lastStop)
{
    vector<int> childrenDP;

    for (auto to : g[node])
    {
        if (to == par) continue;
        if (node == lastStop && marked[to] == true) continue;
        childrenDP.push_back(dfs(to, node, lastStop));
    }

    if (childrenDP.empty()) return 0;

    sort(childrenDP.begin(), childrenDP.end());
    reverse(childrenDP.begin(), childrenDP.end());

    int result = 0;
    for (int i = 0; i < childrenDP.size(); ++i)
    {
        result = max(result, i + 1 + childrenDP[i]);
    }

    return result;
}

int currentAnswer;

bool check(int node1, int node2)
{
    int resultA = dfs(a, -1, node1);
    int resultB = dfs(b, -1, node2);
    currentAnswer = max(resultA, resultB);
    if (resultA < resultB) return true;
    else return false;
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> a >> b;

    for (int i = 1; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfsInit(a, -1);

    int curr = b;
    while (curr != -1)
    {
        path.push_back(curr);
        marked[curr] = true;
        curr = parent[curr];
    }

    reverse(path.begin(), path.end());

    int ans = (1 << 30);

    /*for (int i = 0; i < path.size() - 1; ++i)
    {
        check(path[i], path[i + 1]);
        ans = min(ans, currentAnswer);
    }

    cout << ans << endl;*/

    int l = 0;
    int r = path.size() - 2;

    while (l <= r)
    {
        int mid = (l + r) / 2;

        if (check(path[mid], path[mid + 1]) == true)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }

    if (path.size() == 2)
    {
        check(path[0], path[1]);
        cout << currentAnswer << endl;
    }
    else
    {
        int ans = (1 << 30);
        if (l + 1 < path.size())
        {
            check(path[l], path[l + 1]);
            ans = min(ans, currentAnswer);
        }
        if (l >= 1)
        {
            check(path[l - 1], path[l]);
            ans = min(ans, currentAnswer);
        }
        cout << ans << endl;
    }

    return 0;
}

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