20422022-12-15 21:07:30TomaSajtLogisztikai központcpp17Partially correct 38/5089ms31432 KiB
#include <bits/stdc++.h>
#define speed ios::sync_with_stdio(0);cin.tie(0)
using namespace std;
typedef long long ll;

vector<vector<pair<int, ll>>> g;
vector<ll> dist;
vector<int> par;

void dfs(int u) {
    for (auto [v, w] : g[u]) {
        if (dist[v] != -1) continue;
        dist[v] = dist[u] + w;
        par[v] = u;
        dfs(v);
    }
}

int main() {
    speed;
    int n;
    cin >> n;
    g.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        g[u].push_back({ v,w });
        g[v].push_back({ u,w });
    }
    par.assign(n + 1, -1);
    dist.assign(n + 1, -1);
    dist[1] = 0;
    dfs(1);
    int s = max_element(dist.begin() + 1, dist.end()) - dist.begin();
    par.assign(n + 1, -1);
    dist.assign(n + 1, -1);
    dist[s] = 0;
    dfs(s);
    int e = max_element(dist.begin() + 1, dist.end()) - dist.begin();
    ll diam = dist[e];
    int curr = e;
    map<ll, vector<int>> distLists;
    while (curr != -1) {
        ll currDistS = dist[curr];
        ll currDistE = diam - currDistS;
        distLists[max(currDistS, currDistE)].push_back(curr);
        curr = par[curr];
    }
    auto& [d, l] = *distLists.begin();
    cout << d << '\n' << l.size() << '\n';
    for (auto a : l) cout << a << ' ';
}
SubtaskSumTestVerdictTimeMemory
base38/50
1Accepted0/03ms1828 KiB
2Accepted0/059ms17388 KiB
3Accepted4/42ms2272 KiB
4Partially correct2/42ms2360 KiB
5Accepted4/42ms2612 KiB
6Partially correct2/42ms2556 KiB
7Partially correct2/42ms2620 KiB
8Accepted5/53ms2912 KiB
9Accepted2/289ms20012 KiB
10Accepted2/276ms20196 KiB
11Partially correct1/23ms3244 KiB
12Partially correct1/23ms3584 KiB
13Accepted2/24ms4404 KiB
14Accepted2/28ms5252 KiB
15Accepted2/264ms19404 KiB
16Partially correct1/259ms18836 KiB
17Accepted2/276ms20132 KiB
18Partially correct1/248ms16108 KiB
19Accepted2/254ms20464 KiB
20Partially correct1/383ms31432 KiB