70442023-12-28 21:20:56kukkermanLogisztikai központcpp14Hibás válasz 48/50144ms44500 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

struct El {
    int honnan;
    int hova;
    int 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, int tav) :
        index{ index },
        tav{ tav } {}

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

struct Csucs {
    int szulo = -1;
    int gy_index = -1;
    int 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();
    int 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;

        int 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
base48/50
1Elfogadva0/03ms1684 KiB
2Elfogadva0/0125ms19508 KiB
3Elfogadva4/43ms3140 KiB
4Elfogadva4/43ms3284 KiB
5Elfogadva4/43ms3392 KiB
6Elfogadva4/43ms3628 KiB
7Elfogadva4/43ms3788 KiB
8Elfogadva5/54ms3900 KiB
9Elfogadva2/2134ms23648 KiB
10Elfogadva2/2134ms24468 KiB
11Elfogadva2/23ms6196 KiB
12Elfogadva2/24ms6320 KiB
13Elfogadva2/28ms7060 KiB
14Elfogadva2/214ms8184 KiB
15Elfogadva2/2129ms24008 KiB
16Elfogadva2/2119ms24148 KiB
17Elfogadva2/2130ms26292 KiB
18Hibás válasz0/2101ms23404 KiB
19Elfogadva2/2144ms30596 KiB
20Elfogadva3/3140ms44500 KiB