230892026-01-16 11:51:16RRoliLogisztikai központcpp17Wrong answer 4/50709ms64000 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    auto sr = [](long long a, long long b) {return make_pair(min(a,b), max(a,b));};

    long long n;
    cin >> n;
    vector<unordered_set<long long>> szom(n+1);
    map<pair<long long,long long>,long long> edge;
    for(long long i = 0; i < n-1; i++) {
        long long a, b, c;
        cin >> a >> b >> c;
        szom[a].insert(b);
        szom[b].insert(a);
        edge[sr(a,b)] = c;
    }

    unordered_set<long long> level, volt;
    long long gyok = -1;
    for(long long i = 1; i <= n; i++) {
        if(szom[i].size() == 1) level.insert(i);
        else if(gyok == -1) gyok = i;
    }

    vector<long long> apa(n+1, 0);
    vector<unordered_set<long long>> fia(n+1);
    queue<long long> sor;

    sor.push(gyok);
    volt.insert(gyok);
    while(sor.size() > 0) {
        for(auto i : szom[sor.front()]) {
            if(!volt.count(i)) {
                apa[i] = sor.front();
                fia[sor.front()].insert(i);
                volt.insert(i);
                sor.push(i);
            }
        }
        sor.pop();
    }

    volt.clear();
    vector<set<long long>> alatt(n+1);
    for(auto i : level) {
        alatt[i].insert(0);
        sor.push(i);
        volt.insert(i);
    }

    while(sor.size() > 0) {
        alatt[apa[sor.front()]].insert(*--alatt[sor.front()].end() + edge[sr(sor.front(), apa[sor.front()])]);
        if(apa[sor.front()] != 0 && !volt.count(apa[sor.front()])) {
            sor.push(apa[sor.front()]);
            volt.insert(apa[sor.front()]);
        }
        sor.pop();
    }

    vector<long long> felett(n+1, 0);
    sor.push(gyok);
    while(sor.size() > 0) {
        for(auto i : fia[sor.front()]) {
            if(fia[sor.front()].size() > 1) {
                long long save = *--alatt[i].end() + edge[sr(i, sor.front())];
                alatt[sor.front()].erase(save);
                felett[i] = edge[sr(i, sor.front())] + max(felett[sor.front()], *--alatt[sor.front()].end());
                alatt[sor.front()].insert(save);
            } else {
                felett[i] = edge[sr(i, sor.front())] + felett[sor.front()];
            }
            if(!level.count(i)) sor.push(i);
        }
        sor.pop();
    }

    long long lk = LLONG_MAX;
    for(long long i = 1; i <= n; i++) lk = min(lk, max(*--alatt[i].end(), felett[i]));
    set<long long> ki;
    for(long long i = 1; i <= n; i++) if(max(*--alatt[i].end(), felett[i]) == lk) ki.insert(i);

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

	return 0;
}
SubtaskSumTestVerdictTimeMemory
base4/50
1Accepted0/01ms316 KiB
2Wrong answer0/0651ms59172 KiB
3Accepted4/41ms500 KiB
4Wrong answer0/41ms316 KiB
5Wrong answer0/41ms316 KiB
6Runtime error0/41ms564 KiB
7Runtime error0/41ms520 KiB
8Wrong answer0/54ms1020 KiB
9Runtime error0/2500ms64000 KiB
10Runtime error0/2409ms64000 KiB
11Runtime error0/22ms564 KiB
12Runtime error0/24ms1332 KiB
13Wrong answer0/216ms3536 KiB
14Wrong answer0/239ms6644 KiB
15Wrong answer0/2504ms60072 KiB
16Runtime error0/2316ms56868 KiB
17Wrong answer0/2709ms61772 KiB
18Runtime error0/2331ms45816 KiB
19Runtime error0/2317ms64000 KiB
20Runtime error0/3476ms64000 KiB