2043 2022. 12. 15 21:08:16 TomaSajt Logisztikai központ cpp17 Részben helyes 38/50 103ms 31644 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();
    sort(l.begin(), l.end());
    cout << d << '\n' << l.size() << '\n';
    for (auto a : l) cout << a << ' ';
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 38/50
1 Elfogadva 0/0 3ms 1732 KiB
2 Elfogadva 0/0 64ms 17360 KiB
3 Elfogadva 4/4 2ms 2064 KiB
4 Részben helyes 2/4 2ms 2268 KiB
5 Elfogadva 4/4 2ms 2484 KiB
6 Részben helyes 2/4 2ms 2684 KiB
7 Részben helyes 2/4 2ms 2912 KiB
8 Elfogadva 5/5 3ms 3348 KiB
9 Elfogadva 2/2 68ms 20444 KiB
10 Elfogadva 2/2 71ms 20572 KiB
11 Részben helyes 1/2 3ms 3676 KiB
12 Részben helyes 1/2 3ms 4068 KiB
13 Elfogadva 2/2 4ms 4724 KiB
14 Elfogadva 2/2 8ms 5752 KiB
15 Elfogadva 2/2 65ms 19624 KiB
16 Részben helyes 1/2 61ms 19128 KiB
17 Elfogadva 2/2 67ms 20052 KiB
18 Részben helyes 1/2 50ms 15980 KiB
19 Elfogadva 2/2 59ms 20452 KiB
20 Részben helyes 1/3 103ms 31644 KiB