8488 2024. 01. 18 20:31:55 kukkerman Legtávolabbi leszármazott cpp17 Elfogadva 50/50 28ms 17432 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 Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1828 KiB
2 Elfogadva 0/0 24ms 4400 KiB
3 Elfogadva 1/1 3ms 3344 KiB
4 Elfogadva 3/3 3ms 3576 KiB
5 Elfogadva 3/3 3ms 3656 KiB
6 Elfogadva 1/1 3ms 3752 KiB
7 Elfogadva 1/1 3ms 3912 KiB
8 Elfogadva 1/1 3ms 4012 KiB
9 Elfogadva 2/2 26ms 6628 KiB
10 Elfogadva 3/3 25ms 8132 KiB
11 Elfogadva 3/3 3ms 6772 KiB
12 Elfogadva 4/4 25ms 9136 KiB
13 Elfogadva 4/4 25ms 10416 KiB
14 Elfogadva 3/3 4ms 9492 KiB
15 Elfogadva 3/3 26ms 11784 KiB
16 Elfogadva 3/3 25ms 12960 KiB
17 Elfogadva 3/3 26ms 14344 KiB
18 Elfogadva 4/4 19ms 14740 KiB
19 Elfogadva 4/4 23ms 16104 KiB
20 Elfogadva 4/4 28ms 17432 KiB