95282024-02-22 15:15:17AblablablaLogisztikai központcpp17Hibás válasz 48/50157ms36636 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const ll INF = 2e9 + 7;

vector<vector<pii>> csucsok;

vector<ll> elso;
vector<ll> masodik;
vector<ll> maxInd;
vector<ll> tavok;

ll dfs(ll akt, ll elozo){
    ll felTav = 0;

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

        if(x.first == elozo){
            felTav = x.second;
            continue;
        }

        ll a = dfs(x.first, akt);

        if(elso[akt] < a){
            masodik[akt] = elso[akt];
            elso[akt] = a;
            maxInd[akt] = i;
        } else if(masodik[akt] < a){
            masodik[akt] = a;
        }
    }

    return elso[akt] + felTav;
}

void dfs2(ll akt, ll elozo, ll folotte){
    //cout << akt << " : " << elozo << " " << folotte << "\n";
    if(elso[akt] < folotte){
        masodik[akt] = elso[akt];
        elso[akt] = folotte;
        maxInd[akt] = -1;
    } else if(masodik[akt] < folotte){
        masodik[akt] = folotte;
    }

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

        if(x.first == elozo){
            if(maxInd[akt] == -1){
                maxInd[akt] = i;
            }
            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);
    tavok.assign(n, 0);
    dfs(0, -1);

    dfs2(0, -1, -1);

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

    cout << mini << "\n";
    cout << valasz.size() << "\n";
    for(ll x : valasz){
        cout << x + 1 << " ";
    }
    cout << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base48/50
1Elfogadva0/03ms1812 KiB
2Elfogadva0/0122ms20896 KiB
3Elfogadva4/43ms2192 KiB
4Elfogadva4/43ms2336 KiB
5Elfogadva4/43ms2408 KiB
6Elfogadva4/42ms2408 KiB
7Elfogadva4/43ms2420 KiB
8Elfogadva5/54ms2864 KiB
9Elfogadva2/2135ms24020 KiB
10Elfogadva2/2138ms24152 KiB
11Elfogadva2/23ms3480 KiB
12Elfogadva2/24ms3884 KiB
13Elfogadva2/28ms4568 KiB
14Elfogadva2/214ms5576 KiB
15Elfogadva2/2127ms22812 KiB
16Elfogadva2/2115ms21768 KiB
17Elfogadva2/2134ms23616 KiB
18Hibás válasz0/2100ms18908 KiB
19Elfogadva2/2138ms23980 KiB
20Elfogadva3/3157ms36636 KiB