1114 2022. 03. 03 23:23:16 peti1234 Logisztikai központ cpp14 Elfogadva 50/50 224ms 75100 KiB
#include <bits/stdc++.h>

using namespace std;
const int c=100005;
int n;
long long tav[c], tavid[c];
vector<pair<int, long long> > el[c];
vector<pair<long long, int> > max_tav[c];
bool volt[c], volt2[c];
void dfs(int a) {
    volt[a]=true;
    max_tav[a].push_back({0, a});
    for (auto p:el[a]) {
        int x=p.first;
        long long y=p.second;
        if (!volt[x]) {
            dfs(x);
            max_tav[a].push_back({max_tav[x][0].first+y, max_tav[x][0].second});
            sort(max_tav[a].rbegin(), max_tav[a].rend());
            if (max_tav[a].size()>2) {
                max_tav[a].pop_back();
            }
        }
    }
}
void dfs2(int a) {
    volt2[a]=true;
    tav[a]=max_tav[a][0].first;
    tavid[a]=max_tav[a][0].second;
    for (auto p:el[a]) {
        int x=p.first;
        long long y=p.second;
        if (!volt2[x]) {
            if (tavid[a]!=max_tav[x][0].second) {
                max_tav[x].push_back({max_tav[a][0].first+y, max_tav[a][0].second});
            } else if (max_tav[a].size()>1) {
                max_tav[x].push_back({max_tav[a][1].first+y, max_tav[a][1].second});
            }
            sort(max_tav[x].rbegin(), max_tav[x].rend());
            dfs2(x);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i=1; i<n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        el[a].push_back({b, c});
        el[b].push_back({a, c});
    }
    dfs(1);
    dfs2(1);
    long long ert=tav[1], cnt=0;
    for (int i=1; i<=n; i++) {
        if (tav[i]<ert) {
            ert=tav[i];
            cnt=0;
        }
        if (ert==tav[i]) {
            cnt++;
        }
    }
    cout << ert << "\n";
    cout << cnt << "\n";
    for (int i=1; i<=n; i++) {
        if (tav[i]==ert) {
            cout << i << " ";
        }
    }
    cout << "\n";
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 7ms 11196 KiB
2 Elfogadva 0/0 180ms 37200 KiB
3 Elfogadva 4/4 6ms 12912 KiB
4 Elfogadva 4/4 6ms 12932 KiB
5 Elfogadva 4/4 7ms 12940 KiB
6 Elfogadva 4/4 9ms 12936 KiB
7 Elfogadva 4/4 6ms 12988 KiB
8 Elfogadva 5/5 9ms 13188 KiB
9 Elfogadva 2/2 186ms 41608 KiB
10 Elfogadva 2/2 180ms 42112 KiB
11 Elfogadva 2/2 9ms 15152 KiB
12 Elfogadva 2/2 7ms 15448 KiB
13 Elfogadva 2/2 10ms 16504 KiB
14 Elfogadva 2/2 14ms 18076 KiB
15 Elfogadva 2/2 162ms 41728 KiB
16 Elfogadva 2/2 157ms 41864 KiB
17 Elfogadva 2/2 171ms 45636 KiB
18 Elfogadva 2/2 118ms 40652 KiB
19 Elfogadva 2/2 131ms 45888 KiB
20 Elfogadva 3/3 224ms 75100 KiB