#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector <pair <int, int>> adj[N];
int par[N], dis[N];
queue <int> que;
void BFS(int u, int &diam, int &dist) {
int far = u; diam = 0;
que.push(u); dis[u] = 0; par[u] = -1;
while (que.size()) {
u = que.front(); que.pop();
if (dis[u] > diam) {
diam = dis[u]; far = u;
}
for (auto e : adj[u]) {
int v, w; tie(v, w) = e;
if (v != par[u]) {
dis[v] = dis[u] + w;
par[v] = u; que.push(v);
}
}
}
que.push(u = far);
diam = dis[u] = 0; par[u] = -1;
while (que.size()) {
u = que.front(); que.pop();
if (dis[u] > diam) {
diam = dis[u]; far = u;
}
for (auto e : adj[u]) {
int v, w; tie(v, w) = e;
if (v != par[u]) {
dis[v] = dis[u] + w;
par[v] = u; que.push(v);
}
}
}
dist = INT_MAX; u = far;
while (u >= 0) {
dist = min(dist, max
(dis[u], dis[far] - dis[u]));
u = par[u];
}
}
int travelTime(int n, int m, int l,
vector <int> a, vector <int> b, vector <int> t) {
for (int i = 0; i < m; i++) {
adj[a[i]].emplace_back(b[i], t[i]);
adj[b[i]].emplace_back(a[i], t[i]);
}
memset(dis, -1, sizeof dis);
vector <int> tmp; int res = 0;
for (int i = 0; i < n; i++)
if (dis[i] < 0) {
int diam, dist;
BFS(i, diam, dist);
res = max(res, diam);
tmp.push_back(dist);
}
sort(tmp.begin(), tmp.end());
assert(tmp.size() == n - m);
for (int i = 0; i + 1 < n - m; i++)
tmp[i] += l;
sort(tmp.begin(), tmp.end());
if (n - m > 1)
res = max(res,
tmp[n - m - 1] + tmp[n - m - 2]);
return res;
}
Compilation message
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from dreaming.cpp:2:
dreaming.cpp: In function 'int travelTime(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
dreaming.cpp:68:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
68 | assert(tmp.size() == n - m);
| ~~~~~~~~~~~^~~~~~~~
/tmp/ccNZ6Bdw.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
