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 |