95222024-02-22 14:02:26AblablablaLogisztikai központcpp17Időlimit túllépés 25/501.1s26992 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int INF = 2e9 + 7;

vector<vector<pii>> csucsok;
vector<vector<int>> fel;
vector<int> tavok;
vector<int> euler;
vector<int> elso;
vector<int> masodik;

void dfs(int akt, int elozo, int tav){
    tavok[akt] = tav;
    fel[akt][0] = elozo;
    elso[akt] = euler.size();
    euler.push_back(akt);

    for(pii x : csucsok[akt]){
        if(x.first == elozo) continue;

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

    masodik[akt] = euler.size();
    euler.push_back(akt);
}

bool felmeno(int a, int b){
    if(a == -1 || b == -1){
        return true;
    }
    if(elso[a] < elso[b] && masodik[b] < masodik[a]){
        return true;
    }

    return false;
}

int lca(int a, int b){
    if(tavok[a] < tavok[b]){
        swap(a, b);
    }

    if(felmeno(a, b)){
        return a;
    }

    for(int i = 16; i >= 0; i--){
        if(!felmeno(fel[a][i], b)){
            a = fel[a][i];
        }
    }

    return fel[a][0];
}

int legH = 0;
int kezd, veg;
vector<int> eselyes;
vector<int> eTavok;

int dfs2(int akt, int elozo, int tav){
    int maxi = tav;

    for(pii x : csucsok[akt]){
        if(x.first == elozo) continue;

        maxi = max(maxi, dfs2(x.first, akt, tav + x.second));
    }

    if(maxi == legH){
        eselyes.push_back(akt);
        eTavok.push_back(tav);
    }

    return maxi;
}

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

    csucsok.assign(n, vector<pii>());
    vector<int> befok(n, 0);
    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});
        befok[a]++;
        befok[b]++;
    }

    fel.assign(n, vector<int>(17, 0));
    tavok.assign(n, 0);
    elso.assign(n, 0);
    masodik.assign(n, 0);
    dfs(0, -1, 0);

    for(int j = 1; j < 17; j++){
        for(int i = 0; i < n; i++){
            if(fel[i][j - 1] == -1){
                fel[i][j] = -1;
                continue;
            }

            fel[i][j] = fel[fel[i][j - 1]][j - 1];
        }
    }

    vector<int> levelek;
    for(int i = 0; i < n; i++){
        if(befok[i] == 1){
            levelek.push_back(i);
        }
    }

    for(int i = 0; i < levelek.size(); i++){
        for(int j = i + 1; j < levelek.size(); j++){
            int a = levelek[i];
            int b = levelek[j];

            int tav = tavok[a] + tavok[b] - 2 * tavok[lca(a, b)];

            if(tav > legH){
                legH = tav;
                kezd = a;
                veg = b;
            }
        }
    }

    dfs2(kezd, -1, 0);

    int kHoz = legH, vHez = legH;
    vector<int> varosok;
    for(int i = 0; i < eselyes.size(); i++){
        int a = eTavok[i];
        int b = legH - a;

        if(max(a, b) < max(kHoz, vHez)){
            kHoz = a;
            vHez = b;
            varosok.clear();
            varosok.push_back(eselyes[i]);
        } else if(max(a, b) == max(kHoz, vHez)){
            varosok.push_back(eselyes[i]);
        }
    }

    cout << max(kHoz, vHez) << "\n";
    cout << varosok.size() << "\n";
    for(int x : varosok){
        cout << x + 1 << " ";
    }
    cout << "\n";


    /*int mini = INF;
    vector<int> minInd;
    for(int i = 0; i < n; i++){
        int a = dfs(i, -1);

        if(a < mini){
            mini = a;
            minInd.clear();
            minInd.push_back(i);
        } else if(a == mini){
            minInd.push_back(i);
        }
    }

    cout << mini << "\n";
    cout << minInd.size() << "\n";
    for(int x : minInd){
        cout << x + 1 << " ";
    }
    cout << "\n";*/
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base25/50
1Elfogadva0/03ms1812 KiB
2Időlimit túllépés0/01.1s18372 KiB
3Elfogadva4/43ms2216 KiB
4Részben helyes2/43ms2304 KiB
5Elfogadva4/43ms2448 KiB
6Részben helyes2/43ms2696 KiB
7Részben helyes2/43ms2816 KiB
8Elfogadva5/514ms3088 KiB
9Időlimit túllépés0/21.052s21120 KiB
10Időlimit túllépés0/21.064s21228 KiB
11Részben helyes1/24ms3324 KiB
12Részben helyes1/219ms3876 KiB
13Elfogadva2/2234ms5244 KiB
14Elfogadva2/2913ms7120 KiB
15Időlimit túllépés0/21.072s19968 KiB
16Időlimit túllépés0/21.036s19080 KiB
17Időlimit túllépés0/21.075s20448 KiB
18Időlimit túllépés0/21.052s16440 KiB
19Időlimit túllépés0/21.083s22264 KiB
20Időlimit túllépés0/31.064s26992 KiB