84882024-01-18 20:31:55kukkermanLegtávolabbi leszármazottcpp17Accepted 50/5028ms17432 KiB
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> beolvas(std::istream &be) {
    int n;
    be >> n;

    std::vector<int> szulok(n, -1);
    for (auto i = 1; i < n; i++) {
        int apa, fia;
        be >> apa >> fia;
        szulok[fia - 1] = apa - 1;
    }

    return szulok;
}

void feldolgoz(const std::vector<int> &szulok) {
    const auto n = szulok.size();
    std::vector<int> tav(n, -1);

    const auto gyoker = static_cast<int>(std::find(szulok.cbegin(), szulok.cend(), -1) - szulok.cbegin());

    tav[gyoker] = 0;
    int legtavolabbi = gyoker;
    for (auto i = 0; i < n; i++) {
        if (tav[i] == -1) {
            auto t = 0;
            int j;
            for (j = i; tav[j] == -1; j = szulok[j]) {
                t++;
            }

            t += tav[j];
            if (tav[legtavolabbi] < t) {
                legtavolabbi = i;
            }
            for (j = i; tav[j] == -1; j = szulok[j]) {
                tav[j] = t--;
            }
        }
    }

    std::cout << legtavolabbi + 1 << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    const auto szulok = beolvas(std::cin);
    feldolgoz(szulok);

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1828 KiB
2Accepted0/024ms4400 KiB
3Accepted1/13ms3344 KiB
4Accepted3/33ms3576 KiB
5Accepted3/33ms3656 KiB
6Accepted1/13ms3752 KiB
7Accepted1/13ms3912 KiB
8Accepted1/13ms4012 KiB
9Accepted2/226ms6628 KiB
10Accepted3/325ms8132 KiB
11Accepted3/33ms6772 KiB
12Accepted4/425ms9136 KiB
13Accepted4/425ms10416 KiB
14Accepted3/34ms9492 KiB
15Accepted3/326ms11784 KiB
16Accepted3/325ms12960 KiB
17Accepted3/326ms14344 KiB
18Accepted4/419ms14740 KiB
19Accepted4/423ms16104 KiB
20Accepted4/428ms17432 KiB