#include <bits/stdc++.h>
using namespace std;
#define ll long long
//ifstream in("file.in");
int k = 0;
void DFS_sum(int node, int p, vector<vector<int>> &vec, vector<vector<int>> &cost, vector<int> &Sum, vector<int> &col)
{
col[node] = k;
for (int i = 0; i < vec[node].size(); i++)
{
int vecin = vec[node][i];
if (vecin == p)
continue;
DFS_sum(vecin, node, vec, cost, Sum, col);
Sum[node] = max(Sum[node], Sum[vecin] + cost[node][i]);
}
}
int DFS_Spec(int node, int p, vector<vector<int>> &vec, vector<vector<int>> &cost, vector<int> &down_sum, int &sum1, int &sum2, int &ans)
{
if (vec[node].size() == 0)
return 0;
if (sum2 > sum1)
return ans;
if (vec[node].size() == 1 && p != -1)
return ans;
int path;
for (int i = 0; i < vec[node].size(); i++)
{
int vecin = vec[node][i];
if (vecin == p)
continue;
if (down_sum[vecin] + cost[node][i] == sum1)
{
path = i;
continue;
}
if (down_sum[vecin] + cost[node][i] > sum2)
sum2 = down_sum[vecin] + cost[node][i];
}
if (vec[node].size() > 1 && sum2 == 0)
sum2 = sum1;
sum1 -= cost[node][path];
sum2 += cost[node][path];
ans = min(ans, max(sum2, sum1));
return DFS_Spec(vec[node][path], node, vec, cost, down_sum, sum1, sum2, ans);
}
int graph_hub(int node, vector<vector<int>> &vec, vector<vector<int>> &cost, vector<int> &col)
{
vector<int> down_sum(vec.size(), 0);
DFS_sum(node, -1, vec, cost, down_sum, col);
int sum1 = 0, sum2 = 0;
for (int i = 0; i < vec[node].size(); i++)
sum1 = max(sum1, down_sum[vec[node][i]] + cost[node][i]);
int ans = sum1;
return DFS_Spec(node, -1, vec, cost, down_sum, sum1, sum2, ans);
}
int travelTime(int n, int m, int l, vector<int> A, vector<int> B, vector<int> C)
{
vector<vector<int>> vec(n);
vector<vector<int>> cost(n);
vector<int> col(n, -1);
for (int i = 0; i < m; i++)
{
vec[A[i]].push_back(B[i]);
vec[B[i]].push_back(A[i]);
cost[A[i]].push_back(C[i]);
cost[B[i]].push_back(C[i]);
}
if (m == n - 1)
{
vector<int> down_sum(vec.size(), 0);
DFS_sum(0, -1, vec, cost, down_sum, col);
int sum1 = 0, sum2 = 0;
for (int i = 0; i < vec[0].size(); i++)
{
int S = down_sum[vec[0][i]] + cost[0][i];
if (S > sum1)
{
sum2 = sum1;
sum1 = S;
}
else
sum2 = max(sum2, S);
}
return sum1 + sum2;
}
vector<int> L;
int Max = 0;
for (int i = 0; i < n; i++)
{
if (col[i] == -1)
{
int ans = graph_hub(i, vec, cost, col);
k++;
Max = max(Max, ans);
L.push_back(ans);
}
}
pair<int, int> secMax = make_pair(0, 0);
bool ok = false;
for (int i = 0; i < L.size(); i++)
{
if (L[i] == Max && !ok)
{
ok = true;
continue;
}
if (L[i] > secMax.first)
{
secMax.second = secMax.first;
secMax.first = L[i];
}
else
secMax.second = max(secMax.second, L[i]);
}
return max(Max + l + secMax.first, secMax.first + l * 2 + secMax.second);
}
/*
int main()
{
int n, m, l;
in>> n >> m >> l;
vector<int> A(m), B(m), C(m);
for (int i = 0; i < m; i++)
in>> A[i];
for (int i = 0; i < m; i++)
in>> B[i];
for (int i = 0; i < m; i++)
in>> C[i];
cout<< travelTime(n, m, l, A, B, C);
return 0;
}*/
Compilation message
dreaming.cpp: In function 'void DFS_sum(int, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
dreaming.cpp:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | for (int i = 0; i < vec[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int DFS_Spec(int, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&, int&, int&, int&)':
dreaming.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i = 0; i < vec[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int graph_hub(int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&)':
dreaming.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i = 0; i < vec[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
dreaming.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 0; i < vec[0].size(); i++)
| ~~^~~~~~~~~~~~~~~
dreaming.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (int i = 0; i < L.size(); i++)
| ~~^~~~~~~~~~
dreaming.cpp: In function 'int DFS_Spec(int, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&, int&, int&, int&)':
dreaming.cpp:49:28: warning: 'path' may be used uninitialized in this function [-Wmaybe-uninitialized]
49 | sum1 -= cost[node][path];
| ^
/usr/bin/ld: /tmp/cc40EFeC.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
