1598 | 2022. 11. 28 20:33:34 | kicsiboglar | Logisztikai központ | cpp11 | Hibás válasz 1/50 | 151ms | 25724 KiB |
#include <iostream>
#include <vector>
#include <deque>
#define ll long long
using namespace std;
struct element
{
bool seen = false;
vector <pair<ll, ll> > sz;
ll step, dis, from;
};
ll n, a, b, c, i, j, start;
vector <element> x;
void bfs(ll act)
{
deque<ll> v;
v.push_back(act);
x[act].seen = true;
ll curr;
while (!v.empty())
{
curr = v[0];
v.pop_front();
for (auto& e : x[curr].sz)
{
if (!x[e.first].seen)
{
x[e.first].dis = x[curr].dis + e.second;
x[e.first].from = curr;
x[e.first].seen = true;
x[e.first].step = x[curr].step + 1;
v.push_back(e.first);
}
}
}
}
int main()
{
cin >> n;
x.resize(n + 1);
for (i = 1; i < n; ++i)
{
cin >> a >> b >> c;
x[a].sz.push_back({ b,c });
x[b].sz.push_back({ a,c });
}
bfs(1);
ll maxi = 0;
for (i = 1; i <= n; ++i)
{
if (x[i].dis > maxi)
{
maxi = x[i].dis;
start = i;
}
x[i].seen = false;
x[i].dis = 0;
x[i].step = 0;
}
bfs(start);
ll pos = 0;
maxi = 0;
for (i = 1; i <= n; ++i)
{
if (x[i].dis > maxi)
{
maxi = x[i].dis;
pos = i;
}
x[i].seen = false;
}
ll middle = x[pos].dis / 2,pos2=pos;
while (x[pos2].dis>middle)
{
pos2 = x[pos2].from;
}
cout << pos2;
/*
maxi = max(x[pos].dis - x[pos2].dis, x[pos2].dis);
ll maxii = 999999;
ll o = 0;
if (x[pos].step % 2 != 0)
{
o = x[pos2].from;
maxii = max(x[pos].dis - x[o].dis, x[o].dis);
}
cout << min(maxi, maxii)<<"\n";
if (maxi == maxii)
{
cout << "2\n";
cout << maxi << " " << maxii;
}
else
{
cout << "1\n";
if (maxi < maxii) cout << pos2;
else cout << o;
}*/
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 1/50 | ||||||
1 | Hibás válasz | 0/0 | 3ms | 1680 KiB | |||
2 | Hibás válasz | 0/0 | 126ms | 21008 KiB | |||
3 | Hibás válasz | 0/4 | 2ms | 2056 KiB | |||
4 | Hibás válasz | 0/4 | 2ms | 2288 KiB | |||
5 | Hibás válasz | 0/4 | 2ms | 2336 KiB | |||
6 | Hibás válasz | 0/4 | 2ms | 2448 KiB | |||
7 | Hibás válasz | 0/4 | 2ms | 2472 KiB | |||
8 | Hibás válasz | 0/5 | 3ms | 2896 KiB | |||
9 | Hibás válasz | 0/2 | 151ms | 24192 KiB | |||
10 | Hibás válasz | 0/2 | 144ms | 24540 KiB | |||
11 | Hibás válasz | 0/2 | 3ms | 3448 KiB | |||
12 | Részben helyes | 1/2 | 3ms | 3604 KiB | |||
13 | Hibás válasz | 0/2 | 8ms | 4276 KiB | |||
14 | Hibás válasz | 0/2 | 14ms | 5296 KiB | |||
15 | Hibás válasz | 0/2 | 137ms | 22836 KiB | |||
16 | Hibás válasz | 0/2 | 127ms | 22144 KiB | |||
17 | Hibás válasz | 0/2 | 142ms | 23648 KiB | |||
18 | Hibás válasz | 0/2 | 105ms | 18848 KiB | |||
19 | Hibás válasz | 0/2 | 145ms | 25724 KiB | |||
20 | Hibás válasz | 0/3 | 143ms | 25212 KiB |