#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include "dreaming.h"
using namespace std;
const int maxn = int(1e5)+5, inf = int(2e9)+5;
int n, m, l, D[2][maxn], vis[maxn];
vector<int> cur_comp;
vector<pair<int, int>> guys, graph[maxn];
int dfs(int node, int par, int d, int type)
{
D[type][node] = d;
if(type) cur_comp.push_back(node);
int cur = node;
for(auto it: graph[node])
{
if(it.first != par)
{
int tmp = dfs(it.first, node, d+it.second, type);
if(D[type][cur] < D[type][tmp]) cur = tmp;
}
}
return cur;
}
int travelTime(int _N, int _M, int _L, int _A[], int _B[], int _T[]) {
n = _N, m = _M, l = _L;
for(int i = 0;i < m;i++)
{
graph[_A[i]].push_back({_B[i], _T[i]});
graph[_B[i]].push_back({_A[i], _T[i]});
}
int prev = -1;
for(int i = 0;i < n;i++)
{
if(!vis[i])
{
cur_comp.clear();
int f1 = dfs(i, -1, 0, 0);
int f2 = dfs(f1, -1, 0, 0);
dfs(f2, -1, 0, 1);
pair<int, int> mini = {inf, inf};
for(auto it: cur_comp)
{
mini = min(mini, {max(D[0][it], D[1][it]), it});
vis[it] = 1;
}
guys.push_back(mini);
}
}
sort(guys.rbegin(), guys.rend());
for(auto it: guys)
{
if(prev == -1)
{
prev = it.second;
continue;
}
graph[prev].push_back({it.second, l});
graph[it.second].push_back({prev, l});
cur_comp.clear();
int f1 = dfs(prev, -1, 0, 0);
int f2 = dfs(f1, -1, 0, 0);
dfs(f2, -1, 0, 1);
pair<int, int> mini = {inf, inf};
for(auto it: cur_comp)
{
mini = min(mini, {max(D[0][it], D[1][it]), it});
vis[it] = 1;
}
prev = mini.second;
}
int f1 = dfs(prev, -1, 0, 0);
int f2 = dfs(f1, -1, 0, 0);
return D[0][f2];
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:57:2: error: 'sort' was not declared in this scope
sort(guys.rbegin(), guys.rend());
^~~~
dreaming.cpp:57:2: note: suggested alternative: 'qsort'
sort(guys.rbegin(), guys.rend());
^~~~
qsort
