148262025-02-03 21:44:04RRoliLogisztikai központcpp17Wrong answer 46/501.093s33704 KiB
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second

vector<unordered_map<int,int>> m;
int mapmax(int ind, int k) {
    long long ln = 0;
    for(auto i : m[ind]) {
        if(i.f != k) {
            if(i.s > ln) ln = i.s;
        }
    }
    return ln;
}

int main() {
    int n;
    cin >> n;
    vector<vector<pair<int,int>>> szom(n+1, vector<pair<int,int>>(0));
    vector<int> fok(n+1, 0), tav(n+1, 0);
    vector<bool> volt(n+1, false);
    m.resize(n+1);

    for(int i = 0; i < n-1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        szom[a].push_back(make_pair(b, c));
        szom[b].push_back(make_pair(a, c));
        fok[a]++;
        fok[b]++;
    }

    queue<int>sor;
    for(int i = 1; i <= n; i++) {
        if(fok[i] == 1) {
            sor.push(i);
            volt[i] = true;
            m[i][i] = 0;
        }
    }

    while(!sor.empty()) {
        for(auto j : szom[sor.front()]) {
            if(!volt[j.f]) {
                m[j.f][sor.front()] = mapmax(sor.front(), j.f) + j.s;
                fok[j.f]--;
                if(fok[j.f] == 1) {
                    sor.push(j.f);
                    volt[j.f] = true;
                }
            }
        }
        sor.pop();
    }

    volt.resize(0);
    volt.resize(n+1, false);

    for(int i = 1, megy = 1; i <= n && megy; i++) {
        for(auto j : szom[i]) {
            if(m[i].count(j.f) == 0 && m[j.f].count(i) == 0) {
                volt[i] = true;
                volt[j.f] = true;
                m[i][j.f] = j.s + mapmax(j.f, i);
                m[j.f][i] = j.s + mapmax(i, j.f);
                sor.push(i);
                sor.push(j.f);
                megy = 0;
            }
        }
    }

    while(!sor.empty()) {
        for(auto j : szom[sor.front()]) {
            if(!volt[j.f]) {
                m[j.f][sor.front()] = mapmax(sor.front(), j.f) + j.s;
                sor.push(j.f);
                volt[j.f] = true;
            }
        }
        sor.pop();
    }

    int lk = mapmax(1, -1);
    for(int i = 2; i <= n; i++) lk = min(lk, mapmax(i, -1));

    vector<int> legj;
    for(int i = 1; i <= n; i++)
        if(mapmax(i, -1) == lk) legj.push_back(i);

    cout << lk << '\n' << legj.size() << '\n';
    for(auto i : legj) cout << i << ' ';

	return 0;
}
SubtaskSumTestVerdictTimeMemory
base46/50
1Accepted0/01ms316 KiB
2Accepted0/0301ms29744 KiB
3Accepted4/41ms316 KiB
4Accepted4/41ms316 KiB
5Accepted4/41ms316 KiB
6Accepted4/41ms316 KiB
7Accepted4/41ms316 KiB
8Accepted5/53ms564 KiB
9Accepted2/2326ms33072 KiB
10Accepted2/2259ms33104 KiB
11Accepted2/22ms756 KiB
12Accepted2/23ms820 KiB
13Accepted2/29ms1844 KiB
14Accepted2/219ms3588 KiB
15Accepted2/2250ms30260 KiB
16Accepted2/2231ms28620 KiB
17Accepted2/2333ms31268 KiB
18Wrong answer0/2241ms23860 KiB
19Time limit exceeded0/21.093s33704 KiB
20Accepted3/3250ms31028 KiB