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 |