7045 2023. 12. 28 21:28:49 kukkerman Logisztikai központ cpp14 Elfogadva 50/50 165ms 44228 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

struct El {
    int honnan;
    int hova;
    uint64_t hossz;
};

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

    std::vector<El> elek(n - 1);
    for (auto &el : elek) {
        be >> el.honnan >> el.hova >> el.hossz;
    }

    return elek;
}

struct Szomszed {
    Szomszed() = default;
    Szomszed(int index, uint64_t tav) :
        index{ index },
        tav{ tav } {}

    int index = -1;
    uint64_t tav = 0;
    uint64_t max_tav_nelkule = 0;
};

struct Csucs {
    int szulo = -1;
    int gy_index = -1;
    uint64_t max_tav = 0;
    std::vector<Szomszed> szomszedok;
};

void dfs(int szulo, int gy_index, int akt, std::vector<Csucs> &cs) {
    cs[akt].szulo = szulo;
    cs[akt].gy_index = gy_index;

    const auto &szomszedok = cs[akt].szomszedok;
    const auto n = szomszedok.size();
    uint64_t max_tav = 0;
    for (auto i = 0u; i < n; i++) {
        const auto &akt_szomszed = szomszedok[i];
        if (akt_szomszed.index != szulo) {
            dfs(akt, i, akt_szomszed.index, cs);
            max_tav = std::max(max_tav, cs[akt_szomszed.index].max_tav + akt_szomszed.tav);
        }
    }

    cs[akt].max_tav = max_tav;
}

void bfs(std::vector<Csucs> &cs) {
    std::deque<int> q;    
    q.push_back(0);
    while (!q.empty()) {
        const auto akt = q.front();
        q.pop_front();

        const auto szulo = cs[akt].szulo;
        const auto gy_index = cs[akt].gy_index;

        uint64_t m1, m2 = 0;
        if (szulo != -1) {
            m1 = cs[szulo].szomszedok[gy_index].tav + cs[szulo].szomszedok[gy_index].max_tav_nelkule;
        } else {
            m1 = 0;
        }

        m2 = m1;
        auto &szomszedok = cs[akt].szomszedok;
        for (const auto &akt_szomszed : szomszedok) {
            if (akt_szomszed.index != szulo) {
                const auto akt_tav = cs[akt_szomszed.index].max_tav + akt_szomszed.tav;

                if (m1 <= akt_tav) {
                    m2 = m1;
                    m1 = akt_tav;

                } else if (m2 < akt_tav) {
                    m2 = akt_tav;
                }
            }
        }

        for (auto &akt_szomszed : szomszedok) {
            if (akt_szomszed.index != szulo) {
                const auto akt_tav = cs[akt_szomszed.index].max_tav + akt_szomszed.tav;
                akt_szomszed.max_tav_nelkule = akt_tav < m1 ? m1 : m2;
            }
        }

        if (szulo != -1) {
            cs[akt].max_tav = std::max(cs[akt].max_tav,
                                       cs[szulo].szomszedok[gy_index].max_tav_nelkule + cs[szulo].szomszedok[gy_index].tav);
        }

        for (const auto &akt_szomszed : szomszedok) {
            if (akt_szomszed.index != szulo) {
                q.push_back(akt_szomszed.index);
            }
        }
    }
}

void feldolgoz(const std::vector<El> &elek) {
    const auto n = elek.size() + 1;

    std::vector<Csucs> cs(n);
    for (const auto &e : elek) {
        cs[e.honnan - 1].szomszedok.emplace_back(e.hova - 1, e.hossz);
        cs[e.hova - 1].szomszedok.emplace_back(e.honnan - 1, e.hossz);
    }

    dfs(-1, -1, 0, cs);
    bfs(cs);

    const auto min_tav = std::min_element(cs.cbegin(), cs.cend(), [](const Csucs &cs1, const Csucs &cs2) {
        return cs1.max_tav < cs2.max_tav;
    })->max_tav;

    std::vector<size_t> kozpont_indexek;
    for (auto i = 0u; i < n; i++) {
        if (cs[i].max_tav == min_tav) {
            kozpont_indexek.push_back(i);
        }
    }

    std::cout << min_tav << '\n' << kozpont_indexek.size() << '\n';
    for (auto i : kozpont_indexek) {
        std::cout << i + 1 << ' ';
    }
    std::cout << std::endl;
}

int main() {
    const auto elek = beolvas(std::cin);
    feldolgoz(elek);

    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1816 KiB
2 Elfogadva 0/0 129ms 23496 KiB
3 Elfogadva 4/4 3ms 2396 KiB
4 Elfogadva 4/4 3ms 2508 KiB
5 Elfogadva 4/4 3ms 2664 KiB
6 Elfogadva 4/4 3ms 3008 KiB
7 Elfogadva 4/4 3ms 2972 KiB
8 Elfogadva 5/5 4ms 3440 KiB
9 Elfogadva 2/2 145ms 27276 KiB
10 Elfogadva 2/2 144ms 27236 KiB
11 Elfogadva 2/2 3ms 3232 KiB
12 Elfogadva 2/2 4ms 3760 KiB
13 Elfogadva 2/2 8ms 4556 KiB
14 Elfogadva 2/2 14ms 5912 KiB
15 Elfogadva 2/2 137ms 25536 KiB
16 Elfogadva 2/2 126ms 24308 KiB
17 Elfogadva 2/2 133ms 26068 KiB
18 Elfogadva 2/2 104ms 20636 KiB
19 Elfogadva 2/2 137ms 26512 KiB
20 Elfogadva 3/3 165ms 44228 KiB