#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int radius(int a, int b, int billy, vector<vector<pair<int, int>>> (&edges), vector<int> (&nodes_in_cc), vector<pair<int, int>> (&parent), vector<vector<pair<int, int>>> (&children), vector<vector<pair<int, int>>> (&going_up), vector<int> (&cc))
{
vector<int> patha;
vector<int> pathb;
patha.push_back(a);
int c = a;
while (c!=billy)
{
c = parent[c].first;
patha.push_back(c);
}
pathb.push_back(b);
int d = b;
while (d!=billy)
{
d = parent[d].first;
pathb.push_back(d);
}
int las = billy;
int e = patha.size();
int f = pathb.size();
while ((e>0) and (f>0) and (patha[e-1]==pathb[f-1]))
{
las = patha[e-1];
patha.pop_back();
pathb.pop_back();
e--;
f--;
}
patha.push_back(las);
pathb.push_back(las);
e = patha.size();
f = pathb.size();
vector<int> all_path;
for (int i=0; i<(e-1); i++)
{
all_path.push_back(parent[patha[i]].second);
}
for (int i=f-2; i>=0; i--)
{
all_path.push_back(parent[pathb[i]].second);
}
int k = all_path.size();
vector<int> partial_sums;
int p = 0;
partial_sums.push_back(0);
for (int i=0; i<k; i++)
{
p += all_path[i];
partial_sums.push_back(p);
}
int answer = p+1;
for (int q: partial_sums)
{
int score = max(p-q, q);
answer = min(answer, score);
}
return answer;
}
int tree_radius(int billy, vector<vector<pair<int, int>>> (&edges), vector<int> (&nodes_in_cc), vector<pair<int, int>> (&parent), vector<vector<pair<int, int>>> (&children), vector<vector<pair<int, int>>> (&going_up), vector<int> (&cc))
{
int best_dia = 0;
int best_node_a = billy;
int best_node_b = billy;
int siz = nodes_in_cc.size();
for (int ind = siz-1; ind>=0; ind--)
{
vector<pair<int, int>> choices = going_up[nodes_in_cc[ind]];
sort(choices.begin(), choices.end(), greater<>());
if ((choices.size())>=2)
{
int candidate_length = choices[0].first + choices[1].first;
if (candidate_length > best_dia)
{
best_dia = candidate_length;
best_node_a = choices[0].second;
best_node_b = choices[1].second;
}
}
if ((choices.size())>=1)
{
int candidate_length = choices[0].first;
if (candidate_length > best_dia)
{
best_dia = candidate_length;
best_node_a = choices[0].second;
best_node_b = nodes_in_cc[ind];
}
}
if (ind>0)
{
int tatay = parent[nodes_in_cc[ind]].first;
int bigat = parent[nodes_in_cc[ind]].second;
pair<int, int> inheri;
if ((choices.size())>=1)
{
inheri = {choices[0].first + bigat, choices[0].second};
}
else
{
inheri = {bigat, nodes_in_cc[ind]};
}
going_up[tatay].push_back(inheri);
}
}
return radius(best_node_a, best_node_b, billy, edges, nodes_in_cc, parent, children, going_up, cc);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pair<int, int>>> edges(N);
for (int i=0; i<M; i++)
{
edges[A[i]].push_back({B[i], T[i]});
edges[B[i]].push_back({A[i], T[i]});
}
vector<int> cc(N, -1);
vector<pair<int, int>> parent(N, {-2, 0});
vector<vector<pair<int, int>>> children(N);
vector<vector<pair<int, int>>> going_up(N);//The vector contains one pair for each child. The pair contains {deepest depth, deepest descendant}.
vector<int> hubs;
hubs.reserve(N);
for (int billy = 0; billy < N; billy++)//billabong is such a long word
if (cc[billy] == -1)
{
vector<int> nodes_in_cc;
cc[billy] = billy;
parent[billy] = {-1, 0};
nodes_in_cc.push_back(billy);
int next_ind = 0;
int end_ind = 1;
while (next_ind < end_ind)
{
int curr_node = nodes_in_cc[next_ind];
next_ind++;
for (pair<int, int> edg: edges[curr_node])
{
int neighbor = edg.first;
int weight = edg.second;
if (cc[neighbor] == -1)
{
cc[neighbor] = billy;
parent[neighbor] = {curr_node, weight};
children[curr_node].push_back(edg);
nodes_in_cc.push_back(neighbor);
end_ind++;
}
}
}
hubs.push_back(tree_radius(billy, edges, nodes_in_cc, parent, children, going_up, cc));
}
int hsize = hubs.size();
//for (int i=0; i<hsize; i++)
//cout << hubs[i] << '\n';
if (hsize == 1)
{
return hubs[0];
}
sort(hubs.begin(), hubs.end(), greater());
for (int i=1; i<hsize; i++)
hubs[i] += L;
sort(hubs.begin(), hubs.end(), greater());
return hubs[0]+hubs[1];
}
/*int main()
{
int N, M, L;
cin >> N >> M >> L;
int A[M];
int B[M];
int T[M];
for (int i=0; i<M; i++)
cin >> A[i] >> B[i] >> T[i];
cout << travelTime(N, M, L, A, B, T) << '\n';
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
19400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
19400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
26 ms |
13156 KB |
Output is correct |
| 3 |
Correct |
24 ms |
13092 KB |
Output is correct |
| 4 |
Correct |
24 ms |
13148 KB |
Output is correct |
| 5 |
Correct |
24 ms |
12892 KB |
Output is correct |
| 6 |
Correct |
28 ms |
13656 KB |
Output is correct |
| 7 |
Correct |
25 ms |
13652 KB |
Output is correct |
| 8 |
Correct |
28 ms |
12636 KB |
Output is correct |
| 9 |
Correct |
25 ms |
12636 KB |
Output is correct |
| 10 |
Correct |
30 ms |
13404 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
12 ms |
8896 KB |
Output is correct |
| 13 |
Correct |
11 ms |
9052 KB |
Output is correct |
| 14 |
Correct |
11 ms |
9052 KB |
Output is correct |
| 15 |
Correct |
12 ms |
9008 KB |
Output is correct |
| 16 |
Correct |
12 ms |
9048 KB |
Output is correct |
| 17 |
Correct |
12 ms |
9052 KB |
Output is correct |
| 18 |
Correct |
12 ms |
9052 KB |
Output is correct |
| 19 |
Correct |
12 ms |
9052 KB |
Output is correct |
| 20 |
Correct |
0 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Correct |
0 ms |
604 KB |
Output is correct |
| 23 |
Correct |
11 ms |
9052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
19400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
