#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e9,LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define pb push_back
#define PRINTvec(arr) { cerr<<#arr<<"="; for(auto h:arr) cerr<<h<<" "; cerr<<endl; }
#define int long long
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<int> adj[N+1];
map<pair<int,int>,int> edge;
for(int i=0;i<M;i++){
int u=A[i],v=B[i],w=T[i];
u++; v++;
adj[u].pb(v);
adj[v].pb(u);
edge[{u,v}]=w;
edge[{v,u}]=w;
}
vector<int> trees[N+1];
vector<bool> vis(N+1,false);
int idx=1;
function<void(int,int)> dfs=[&](int node,int prev){
vis[node]=true;
trees[idx].pb(node);
for(auto v:adj[node]) if(v!=prev) dfs(v,node);
};
for(int i=1;i<=N;i++){
if(!vis[i]){
dfs(i,-1);
idx++;
}
}
vector<ll> nadstablo_udaljenost(N+1),podstablo_udaljenost1(N+1),podstablo_udaljenost2(N+1);
vector<ll> udaljenost(N+1),dubina(N+1);
function<void(int,int)> dfs1=[&](int node,int prev){
podstablo_udaljenost1[node]=0; podstablo_udaljenost2[node]=0;
if(prev!=-1) dubina[node]=dubina[prev]+1;
else dubina[node]=0;
vector<ll> tmp; tmp.pb(0); tmp.pb(0);
for(auto v:adj[node]){
if(v!=prev){
dfs1(v,node);
tmp.pb(podstablo_udaljenost1[v]+edge[{node,v}]);
}
}
sort(all(tmp),greater<int>());
podstablo_udaljenost1[node]=tmp[0]; podstablo_udaljenost2[node]=tmp[1];
};
function<void(int,int)> dfs2=[&](int node,int prev){
nadstablo_udaljenost[node]=0;
if(prev!=-1){
nadstablo_udaljenost[node]=nadstablo_udaljenost[prev]+edge[{prev,node}];
}
for(auto v:adj[prev]){
if(dubina[v]>dubina[prev] && v!=node){
nadstablo_udaljenost[node]=max(nadstablo_udaljenost[node],podstablo_udaljenost1[v]+edge[{v,prev}]+edge[{prev,node}]);
}
}
for(auto v:adj[node]) if(v!=prev) dfs2(v,node);
udaljenost[node]=max(nadstablo_udaljenost[node],podstablo_udaljenost1[node]);
};
vector<pii> all_trees;
for(int i=1;i<idx;i++){
int node=0,val=LINF;
for(auto v:trees[i]){
if(udaljenost[v]<=val){
val=udaljenost[v]; node=v;
}
}
all_trees.pb({val,node});
}
sort(all(all_trees),greater<pair<ll,ll>>());
for(int i=1;i<(all_trees.size());i++){
int node=all_trees[i].se;
int first=all_trees[0].se;
adj[node].pb(first); adj[first].pb(node);
edge[{node,first}]=L; edge[{first,node}]=L;
}
/*
int node=0; ll val=LINF;
for(int i=1;i<idx;i++){
int root=trees[i][0];
dfs1(root,-1);
dfs2(root,-1);
if(i==1){
for(auto v:trees[i]){
if(udaljenost[v]<=val){
val=udaljenost[v]; node=v;
}
}
}
else{
int tmp_node=0,tmp_val=INF;
for(auto v:trees[i]){
if(udaljenost[v]<=tmp_val){
tmp_val=udaljenost[v]; tmp_node=v;
}
}
adj[tmp_node].pb(node); adj[node].pb(tmp_node);
edge[{tmp_node,node}]=L; edge[{node,tmp_node}]=L;
}
}
*/
/*
for(int i=1;i<idx;i++){
PRINTvec(trees[i]);
for(auto v:trees[i]){
cout<<"nadstablo_udaljenost["<<v<<"]="<<nadstablo_udaljenost[v]<<endl;
cout<<"podstablo_udaljenost1["<<v<<"]="<<podstablo_udaljenost1[v]<<endl;
cout<<"podstablo_udaljenost2["<<v<<"]="<<podstablo_udaljenost2[v]<<endl;
cout<<"udaljenost["<<v<<"]="<<udaljenost[v]<<endl;
cout<<"dubina["<<v<<"]="<<dubina[v]<<endl;
cout<<endl;
}
cout<<endl<<endl;
}
*/
dfs1(1,-1);
ll diametar=0;
for(int node=1;node<=N;node++){
diametar=max(diametar,podstablo_udaljenost1[node]+podstablo_udaljenost2[node]);
}
return diametar;
}
Compilation message
dreaming.cpp: In function 'long long int travelTime(long long int, long long int, long long int, long long int*, long long int*, long long int*)':
dreaming.cpp:92:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i=1;i<(all_trees.size());i++){
| ~^~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccKka2ve.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
