#include <vector>
#include <algorithm>
using namespace std;
int const N=1e5+10;
vector<pair<int,int>>nei[N]={};
vector<int>heads;
bool vis[N]={};
int cost[N]={};
void dfs(int n)
{
vis[n]=1;
for (auto [i,w]:nei[n])
{
if (!vis[i])
{
cost[n]+=w;
dfs(i);
cost[n]+=cost[i];
}
}
}
vector<pair<int,int>>cur={};
void getroot(int n,int pa,int root)
{
int f=0;
for (auto [i,w]:nei[n])
{
if (i!=pa)
{
f=max(f,cost[i]);
getroot(i,n,root);
}
else
f=max(f,cost[pa]-cost[n]);
}
cur.push_back({f,n});
}
void dfs1(int n,int m=-1)
{
for (auto [i,w]:nei[n])
if (i!=m)
{
cost[i]+=cost[n];
cost[i]+=w;
dfs1(i,n);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
for (int i=0;i<m;i++)
{
nei[a[i]].push_back({b[i],t[i]});
nei[b[i]].push_back({a[i],t[i]});
}
for (int i=0;i<n;i++)
{
if (!vis[i])
{
heads.push_back(i);
dfs(i);
}
}
for (int i=0;i<n;i++)
vis[i]={};
vector<pair<int,int>>new_head;
for (auto i:heads)
{
getroot(i,-1,i);
sort(begin(cur),end(cur));
new_head.push_back(cur[0]);
cur={};
}
sort(begin(new_head),end(new_head));
reverse(begin(new_head),end(new_head));
for (int i=1;i<new_head.size();i++)
{
nei[new_head[0].second].push_back({new_head[i].second,l});
nei[new_head[i].second].push_back({new_head[0].second,l});
}
for (int i=0;i<n;i++)
cost[i]=0;
dfs1(0);
new_head={};
for (int i=0;i<n;i++)
{
new_head.push_back({cost[i],i});
cost[i]=0;
}
sort(begin(new_head),end(new_head));
reverse(begin(new_head),end(new_head));
dfs1(new_head[0].second);
new_head={};
for (int i=0;i<n;i++)
{
new_head.push_back({cost[i],i});
cost[i]=0;
}
sort(begin(new_head),end(new_head));
reverse(begin(new_head),end(new_head));
return new_head[0].first;
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:75:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i=1;i<new_head.size();i++)
| ~^~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccCShc1f.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
