9587 2024. 02. 23 13:17:20 Ablablabla Logisztikai központ cpp17 Elfogadva 50/50 150ms 34824 KiB
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll, ll> pii;

vector<vector<pii>> csucsok;
vector<ll> elso;
vector<ll> masodik;
vector<ll> maxInd;

ll dfs(ll akt, ll elozo){
    for(ll i = 0; i < csucsok[akt].size(); i++){
        pii x = csucsok[akt][i];

        if(x.first == elozo) continue;

        ll tav = dfs(x.first, akt) + x.second;

        if(tav >= elso[akt]){
            masodik[akt] = elso[akt];
            elso[akt] = tav;
            maxInd[akt] = i;
        } else if(tav > masodik[akt]){
            masodik[akt] = tav;
        }
    }

    return elso[akt];
}

void dfs2(ll akt, ll elozo, ll folotte){
    if(folotte >= elso[akt]){
        masodik[akt] = elso[akt];
        elso[akt] = folotte;
        maxInd[akt] = -1;
    } else if(folotte > masodik[akt]){
        masodik[akt] = folotte;
    }

    for(ll i = 0; i < csucsok[akt].size(); i++){
        pii x = csucsok[akt][i];

        if(x.first == elozo) continue;

        dfs2(x.first, akt, (maxInd[akt] == i ? masodik[akt] : elso[akt]) + x.second);
    }
}

int main(){
    ll n;
    cin >> n;

    csucsok.assign(n, vector<pii>());
    for(ll i = 0; i < n - 1; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        a--; b--;

        csucsok[a].push_back({b, c});
        csucsok[b].push_back({a, c});
    }

    elso.assign(n, 0);
    masodik.assign(n, 0);
    maxInd.assign(n, 0);
    dfs(0, -1);

    dfs2(0, -1, 0);

    ll mini = LONG_MAX;
    vector<ll> indexek;
    for(ll i = 0; i < n; i++){
        if(elso[i] < mini){
            mini = elso[i];
            indexek.clear();
            indexek.push_back(i);
        } else if(elso[i] == mini){
            indexek.push_back(i);
        }
    }

    assert(mini != LONG_MAX);
    cout << mini << "\n";
    cout << indexek.size() << "\n";
    for(ll x : indexek){
        cout << x + 1 << " ";
    }
    cout << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1960 KiB
2 Elfogadva 0/0 128ms 19524 KiB
3 Elfogadva 4/4 3ms 2160 KiB
4 Elfogadva 4/4 3ms 2328 KiB
5 Elfogadva 4/4 2ms 2380 KiB
6 Elfogadva 4/4 3ms 2508 KiB
7 Elfogadva 4/4 3ms 2628 KiB
8 Elfogadva 5/5 4ms 2692 KiB
9 Elfogadva 2/2 138ms 22000 KiB
10 Elfogadva 2/2 138ms 22004 KiB
11 Elfogadva 2/2 3ms 2896 KiB
12 Elfogadva 2/2 4ms 3360 KiB
13 Elfogadva 2/2 8ms 4140 KiB
14 Elfogadva 2/2 14ms 5220 KiB
15 Elfogadva 2/2 136ms 21292 KiB
16 Elfogadva 2/2 125ms 20592 KiB
17 Elfogadva 2/2 137ms 22128 KiB
18 Elfogadva 2/2 104ms 17404 KiB
19 Elfogadva 2/2 144ms 22528 KiB
20 Elfogadva 3/3 150ms 34824 KiB