#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > adj[100000];
map<pair<int, int>, int> edges;
vector<int> subgraphs[100000];
bool visited[100000]={false};
void findsubgraphs(int x, int k)
{
if (visited[x])
return;
visited[x]=true;
subgraphs[k].push_back(x);
for (auto edge : adj[x])
if (!visited[edge.first])
findsubgraphs(edge.first, k);
return;
}
pair<int, int> findfarthest(int x, int t)
{
pair<int, int> farthest={0, x};
for (auto edge : adj[x])
{
int y=edge.first;
int v=edge.second;
if (y==t)
continue;
auto t=findfarthest(y, x);
if (t.first+v>farthest.first)
farthest={t.first+v, t.second};
}
return farthest;
}
bool findpath(int x, int t, int y, bool valid, vector<int> &path)
{
path.push_back(x);
if (x==y)
return true;
for (auto edge : adj[x])
{
if (edge.first==t)
continue;
if (findpath(edge.first, x, y, valid, path))
return true;
}
path.pop_back();
return false;
}
int travelTime(int n, int m, int l, int edgex[], int edgey[],int edgev[])
{
int k=0, x, y, v, sum, maxdistance=0, i, j;
for (i=0; i<m; i++)
{
x=edgex[i];
y=edgey[i];
v=edgev[i];
adj[x].push_back({y, v});
adj[y].push_back({x, v});
edges[{x, y}]=v;
edges[{y, x}]=v;
}
for (i=0; i<m; i++)
{
if (visited[i])
continue;
findsubgraphs(i, k);
k=k+1;
}
pair<int, int> distances[k];
for (i=0; i<k; i++)
{
x=findfarthest(subgraphs[i][0], -1).second;
y=findfarthest(x, -1).second;
vector<int> path;
findpath(x, -1, y, false, path);
sum=0;
for (j=0; j<path.size()-1; j++)
sum=sum+edges[{path[j], path[j+1]}];
distances[i].first=0;
distances[i].second=sum;
for (j=0; j<path.size()-1; j++)
{
int nextsum1=distances[i].first+edges[{path[j], path[j+1]}];
int nextsum2=distances[i].second-edges[{path[j], path[j+1]}];
if (abs(nextsum1-nextsum2)>abs(distances[i].first-distances[i].second))
break;
distances[i].first=nextsum1;
distances[i].second=nextsum2;
}
if (distances[i].second>distances[i].first)
swap(distances[i].first, distances[i].second);
}
sort(distances, distances+k);
maxdistance=distances[k-1].first+distances[k-1].second;
if (k>=2)
maxdistance=max(maxdistance, distances[k-2].first+distances[k-1].first+l);
if (k>=3)
maxdistance=max(maxdistance, distances[k-2].first+distances[k-3].first+2*l);
return maxdistance;
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (j=0; j<path.size()-1; j++)
| ~^~~~~~~~~~~~~~
dreaming.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (j=0; j<path.size()-1; j++)
| ~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccPPZl2b.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
