#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
ifstream in("file.in");
int k = 0;
void DFS_sum(int node, int p, vector<int> &sum, vector<vector<int>> &vec, vector<vector<int>> &cost, vector<int> &col)
{
col[node] = k;
for (int i = 0; i < vec[node].size(); i++)
{
if (vec[node][i] == p)
continue;
DFS_sum(vec[node][i], node, sum, vec, cost, col);
sum[node] = max(sum[node], sum[vec[node][i]] + cost[node][i]);
}
}
void DFS_sec(int node, int p, int sum, vector<int> &best, vector<vector<int>> &vec, vector<vector<int>> &cost)
{
best[node] = sum;
for (int i = 0; i < vec[node].size(); i++)
{
if (vec[node][i] == p)
continue;
DFS_sec(vec[node][i], node, sum + cost[node][i], best, vec, cost);
}
}
void DFS_main(int node, int p, int main, int sec, vector<int> &sum, vector<int> &best, vector<vector<int>> &vec, vector<vector<int>> &cost)
{
best[node] = main;
int path = -1;
for (int i = 0; i < vec[node].size(); i++)
{
int temp = sum[vec[node][i]] + cost[node][i];
if (vec[node][i] == p)
continue;
if (temp > sec && (temp != main || path != -1))
sec = temp;
if (temp == main)
path = i;
else
DFS_sec(vec[node][i], node, main + cost[node][i], best, vec, cost);
}
if (path == -1)
return;
main = sum[vec[node][path]];
sec += cost[node][path];
if (sec > main)
DFS_sec(vec[node][path], node, sec, best, vec, cost);
else
DFS_main(vec[node][path], node, main, sec, sum, best, vec, cost);
}
int graph_hub(int node, vector<vector<int>> &vec, vector<vector<int>> &cost, vector<int> &col)
{
vector<int> sum(vec.size(), 0);
DFS_sum(node, -1, sum, vec, cost, col);
int MAX = 0, sec = 0;
for (int i = 0; i < vec[node].size(); i++)
{
int temp = sum[vec[node][i]] + cost[node][i];
if (temp > MAX)
{
sec = MAX;
MAX = temp;
}
else
sec = max(sec, temp);
}
vector<int> best(vec.size(), 1000 * 1000 * 1000);
DFS_main(node, -1, MAX, sec, sum, best, vec, cost);
int Min = best[0];
for (int i = 0; i < best.size(); i++)
Min = min(best[i], Min);
return Min;
}
int travelTime(int N, int M, int L, int A[], int B[], int C[])
{
vector<int> col(N, -1);
vector<vector<int>> vec(N), cost(N);
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> sum(N, 0);
DFS_sum(0, -1, sum, vec, cost, col);
int unos = 0, dos = 0;
for (int i = 0; i < vec[0].size(); i++)
{
int temp = sum[vec[0][i]] + cost[0][i];
if (temp > unos)
{
dos = unos;
unos = temp;
}
else
dos = max(dos, temp);
}
return unos + dos;
}
vector<int> hub_l;
for (int i = 0; i < N; i++)
if (col[i] = -1)
{
hub_l.push_back(graph_hub(i, vec, cost, col));
k++;
}
int unos = 0, dos = 0, tres = 0;
for (int i = 0; i < hub_l.size(); i++)
unos = max(unos, hub_l[i]);
for (int i = 0; i < hub_l.size(); i++)
if (hub_l[i] != unos)
dos = max(dos, hub_l[i]);
for (int i = 0; i < hub_l.size(); i++)
if (hub_l[i] != unos && hub_l[i] != dos)
tres = max(tres, hub_l[i]);
if (M == N - 2)
return unos + L + dos;
return max(unos + L + dos, dos + 2 * L + tres);
}
/*
int main()
{
int N, M, L;
in>> N >> M >> L;
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<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&)':
dreaming.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for (int i = 0; i < vec[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void DFS_sec(int, int, int, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
dreaming.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (int i = 0; i < vec[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void DFS_main(int, int, int, int, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
dreaming.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | 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:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 0; i < vec[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i = 0; i < best.size(); i++)
| ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:109:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (int i = 0; i < vec[0].size(); i++)
| ~~^~~~~~~~~~~~~~~
dreaming.cpp:125:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
125 | if (col[i] = -1)
dreaming.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (int i = 0; i < hub_l.size(); i++)
| ~~^~~~~~~~~~~~~~
dreaming.cpp:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for (int i = 0; i < hub_l.size(); i++)
| ~~^~~~~~~~~~~~~~
dreaming.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for (int i = 0; i < hub_l.size(); i++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1063 ms |
21148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1063 ms |
21148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1049 ms |
11036 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1063 ms |
21148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
