70452023-12-28 21:28:49kukkermanLogisztikai központcpp14Elfogadva 50/50165ms44228 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ÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1816 KiB
2Elfogadva0/0129ms23496 KiB
3Elfogadva4/43ms2396 KiB
4Elfogadva4/43ms2508 KiB
5Elfogadva4/43ms2664 KiB
6Elfogadva4/43ms3008 KiB
7Elfogadva4/43ms2972 KiB
8Elfogadva5/54ms3440 KiB
9Elfogadva2/2145ms27276 KiB
10Elfogadva2/2144ms27236 KiB
11Elfogadva2/23ms3232 KiB
12Elfogadva2/24ms3760 KiB
13Elfogadva2/28ms4556 KiB
14Elfogadva2/214ms5912 KiB
15Elfogadva2/2137ms25536 KiB
16Elfogadva2/2126ms24308 KiB
17Elfogadva2/2133ms26068 KiB
18Elfogadva2/2104ms20636 KiB
19Elfogadva2/2137ms26512 KiB
20Elfogadva3/3165ms44228 KiB