#include <iostream>
#include <vector>
#include <set>
#include "dreaming.h"
using namespace std;
const int maxN = 1e5 + 5;
long long dist[2][maxN], visited[maxN];
vector<pair<long long, long long> > adj[maxN];
vector<int> component;
multiset<pair<long long, long long > > comps;
pair<long long, int> dfs(int node, int parent, long long cur_dist, long long *store, bool need_add){
visited[node] = 1;
if (need_add) component.push_back(node);
else store[node] = cur_dist;
pair<long long, int> ans = make_pair(cur_dist, node);
for (pair<int, int> child: adj[node]){
if (child.first == parent) continue;
ans = max(ans, dfs(child.first, node, cur_dist+child.second, store, need_add));
}
return ans;
}
long long travelTime(int n, int m, long long L, int a[], int b[], int t[]){
for (int i = 0; i < m; i++){
adj[a[i]].push_back(make_pair(b[i], t[i]));
adj[b[i]].push_back(make_pair(a[i], t[i]));
}
for (int i = 0; i < n; i++){
if (visited[i]) continue;
component.clear();
pair<long long, int> furthest = dfs(i, -1, 0, dist[0], true);
pair<long long, int> next_furthest = dfs(furthest.second, -1, 0, dist[0], false);
dfs(next_furthest.second, -1, 0, dist[1], false);
long long mini_max = 1e18;
for (int node: component) mini_max = min(mini_max, max(dist[0][node], dist[1][node]));
comps.insert(make_pair(mini_max, next_furthest.first));
}
while(comps.size() > 1){
pair<long long, long long> first = *comps.begin();
pair<long long, long long> second = *comps.rbegin();
comps.erase(comps.begin());
comps.erase(--comps.end());
pair<long long, long long> new_comp;
new_comp.first = min(max(first.first, second.first + L), max(second.first, first.first + L));
new_comp.second = max(first.second, max(second.second, first.first + second.first + L));
comps.insert(new_comp);
}
pair<long long, long long> ans = *comps.begin();
cout << ans.second << endl;
}
Compilation message
dreaming.cpp: In function 'long long int travelTime(int, int, long long int, int*, int*, int*)':
dreaming.cpp:67:1: warning: no return statement in function returning non-void [-Wreturn-type]
67 | }
| ^
/usr/bin/ld: /tmp/cc7f7vS1.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
