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 |