1115 2022. 03. 03 23:30:20 peti1234 Logisztikai központ cpp14 Elfogadva 50/50 252ms 76076 KiB
#include <bits/stdc++.h>

using namespace std;
const int c=100005;
int n;
long long tav[c], tavid[c];
vector<pair<int, long long> > el[c];
vector<pair<long long, int> > max_tav[c];
bool volt[c], volt2[c];
void dfs(int a) {
    volt[a]=true;

    // a max_tav az a-bol elerheto legnagyobb tavolsagokat tarolja (tavolsak, csucs) formaban, forditva rendezve (ez igy nem tul elegans)
    max_tav[a].push_back({0, a});
    // onmagatol 0 tavol van

    for (auto p:el[a]) {
        int x=p.first;
        long long y=p.second;
        if (!volt[x]) {
            dfs(x);
            max_tav[a].push_back({max_tav[x][0].first+y, max_tav[x][0].second});
            // a gyerekeitol tavoli csucsokat kell figyelni

            sort(max_tav[a].rbegin(), max_tav[a].rend());
            if (max_tav[a].size()>2) {
                max_tav[a].pop_back();
            }
            // eleg a ket legjobbat megjegyzni, talan felesleges (szinten nem tul szep)
        }
    }
}
void dfs2(int a) {
    // egy hasonlo melysegi bejaras
    volt2[a]=true;
    tav[a]=max_tav[a][0].first;
    // tav[a] a lenyeg

    tavid[a]=max_tav[a][0].second;
    for (auto p:el[a]) {
        int x=p.first;
        long long y=p.second;
        if (!volt2[x]) {
            // a kovetkezo csucshoz kell megtalalni a legtavolabbi csucsot (ami a-n keresztul megy)
            if (tavid[a]!=max_tav[x][0].second) {
                // ha nem az (a-x) elen ment at ketszer, akkor a legnagyobb
                max_tav[x].push_back({max_tav[a][0].first+y, max_tav[a][0].second});
            } else if (max_tav[a].size()>1) {
                // egyebkent a masodik legnagyobbat kell tovabb vinni
                max_tav[x].push_back({max_tav[a][1].first+y, max_tav[a][1].second});
            }
            sort(max_tav[x].rbegin(), max_tav[x].rend());
            dfs2(x);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i=1; i<n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        el[a].push_back({b, c});
        el[b].push_back({a, c});
    }
    // szomszedok listaja (csucs, tavolsag) parban

    dfs(1);
    // legyen a fanak 1 a gyokere, es hatarozzuk meg minden csucsban a ket alatta levo legtavolabbi csucsot

    dfs2(1);
    // ezekkel az informaciokkal mar ki lehet talalni, minden csucsra, hogy milyen messze van a tole legmesszebb levo csucs


    // a tav tombben van az osszes fontos informacio
    long long ert=tav[1], cnt=0;
    for (int i=1; i<=n; i++) {
        if (tav[i]<ert) {
            ert=tav[i];
            cnt=0;
        }
        if (ert==tav[i]) {
            cnt++;
        }
    }
    cout << ert << "\n";
    cout << cnt << "\n";
    for (int i=1; i<=n; i++) {
        if (tav[i]==ert) {
            cout << i << " ";
        }
    }
    cout << "\n";
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 7ms 11280 KiB
2 Elfogadva 0/0 144ms 37136 KiB
3 Elfogadva 4/4 6ms 12924 KiB
4 Elfogadva 4/4 6ms 12928 KiB
5 Elfogadva 4/4 8ms 12928 KiB
6 Elfogadva 4/4 6ms 12936 KiB
7 Elfogadva 4/4 6ms 12960 KiB
8 Elfogadva 5/5 8ms 13232 KiB
9 Elfogadva 2/2 168ms 41612 KiB
10 Elfogadva 2/2 159ms 43204 KiB
11 Elfogadva 2/2 6ms 16244 KiB
12 Elfogadva 2/2 8ms 16660 KiB
13 Elfogadva 2/2 9ms 17680 KiB
14 Elfogadva 2/2 14ms 19180 KiB
15 Elfogadva 2/2 149ms 42808 KiB
16 Elfogadva 2/2 142ms 42904 KiB
17 Elfogadva 2/2 157ms 46616 KiB
18 Elfogadva 2/2 127ms 41632 KiB
19 Elfogadva 2/2 130ms 46964 KiB
20 Elfogadva 3/3 252ms 76076 KiB