84882024-01-18 20:31:55kukkermanLegtávolabbi leszármazottcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1828 KiB
2Elfogadva0/024ms4400 KiB
3Elfogadva1/13ms3344 KiB
4Elfogadva3/33ms3576 KiB
5Elfogadva3/33ms3656 KiB
6Elfogadva1/13ms3752 KiB
7Elfogadva1/13ms3912 KiB
8Elfogadva1/13ms4012 KiB
9Elfogadva2/226ms6628 KiB
10Elfogadva3/325ms8132 KiB
11Elfogadva3/33ms6772 KiB
12Elfogadva4/425ms9136 KiB
13Elfogadva4/425ms10416 KiB
14Elfogadva3/34ms9492 KiB
15Elfogadva3/326ms11784 KiB
16Elfogadva3/325ms12960 KiB
17Elfogadva3/326ms14344 KiB
18Elfogadva4/419ms14740 KiB
19Elfogadva4/423ms16104 KiB
20Elfogadva4/428ms17432 KiB