95272024-02-22 15:14:21AblablablaLogisztikai központcpp17Wrong answer 48/50134ms29388 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int INF = 2e9 + 7;

vector<vector<pii>> csucsok;

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

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

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

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

        int 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(int akt, int elozo, int 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(int 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(){
    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);
    tavok.assign(n, 0);
    dfs(0, -1);

    dfs2(0, -1, -1);

    int mini = INF;
    vector<int> valasz;
    for(int 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(int x : valasz){
        cout << x + 1 << " ";
    }
    cout << "\n";
}
SubtaskSumTestVerdictTimeMemory
base48/50
1Accepted0/03ms1812 KiB
2Accepted0/0115ms15576 KiB
3Accepted4/43ms2272 KiB
4Accepted4/43ms2484 KiB
5Accepted4/43ms2696 KiB
6Accepted4/43ms2784 KiB
7Accepted4/43ms3044 KiB
8Accepted5/54ms3092 KiB
9Accepted2/2128ms18212 KiB
10Accepted2/2126ms18276 KiB
11Accepted2/23ms3192 KiB
12Accepted2/24ms3532 KiB
13Accepted2/28ms4400 KiB
14Accepted2/214ms5168 KiB
15Accepted2/2120ms17556 KiB
16Accepted2/2112ms16916 KiB
17Accepted2/2125ms17884 KiB
18Wrong answer0/298ms14848 KiB
19Accepted2/2130ms19436 KiB
20Accepted3/3134ms29388 KiB