95862024-02-23 13:12:27AblablablaLogisztikai központcpp17Wrong answer 48/50134ms28372 KiB
#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

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

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

        if(x.first == elozo) continue;

        int 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(int akt, int elozo, int folotte){
    if(folotte >= elso[akt]){
        masodik[akt] = elso[akt];
        elso[akt] = folotte;
        maxInd[akt] = -1;
    } else if(folotte > masodik[akt]){
        masodik[akt] = folotte;
    }

    for(int 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(){
    int n;
    cin >> n;

    csucsok.assign(n, vector<pii>());
    for(int i = 0; i < n - 1; i++){
        int 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);

    int mini = INT_MAX;
    vector<int> indexek;
    for(int 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 != INT_MAX);
    cout << mini << "\n";
    cout << indexek.size() << "\n";
    for(int x : indexek){
        cout << x + 1 << " ";
    }
    cout << "\n";
}
SubtaskSumTestVerdictTimeMemory
base48/50
1Accepted0/03ms1680 KiB
2Accepted0/0120ms14852 KiB
3Accepted4/43ms2208 KiB
4Accepted4/43ms2136 KiB
5Accepted4/43ms2364 KiB
6Accepted4/43ms2456 KiB
7Accepted4/43ms2600 KiB
8Accepted5/54ms3000 KiB
9Accepted2/2128ms17196 KiB
10Accepted2/2128ms17196 KiB
11Accepted2/23ms3136 KiB
12Accepted2/24ms3432 KiB
13Accepted2/28ms3924 KiB
14Accepted2/214ms4660 KiB
15Accepted2/2119ms16356 KiB
16Accepted2/2109ms15956 KiB
17Accepted2/2125ms17252 KiB
18Wrong answer0/297ms14096 KiB
19Accepted2/2127ms18452 KiB
20Accepted3/3134ms28372 KiB