#include<bits/stdc++.h>
#include "dreaming.h"
#define ll long long
#define pll pair<ll,ll>
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define all(v) v.begin(),v.end()
const int sz = 1e5+5;
const ll inf = 1000000000000000;
using namespace std;
vector<pair<ll,ll>> adj[sz];
ll dis[sz][2], center, v1, v2, mx, cnt = -1;
bool used[sz];
vector<vector<ll>> path;
void trav(ll node){
used[node] = 1;
path[cnt].push_back(node);
for(pll edge: adj[node]){
if(!used[edge.fi]){
dfs(egde.fi);
}
}
}
void dfs(ll node, ll we, ll p){
if(we > mx){
v2 = node;
mx = we;
}
for(pll edge: adj[node]){
if(edge.fi != p){
dfs(edge.fi, we + edge.se, node);
}
}
}
void caldis(ll node, ll we, ll p, ll type){
dis[node][type] = we;
for(pll edge: adj[node]){
if(edge.fi != p){
dfs(edge.fi);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
ll n = N, m = M, i, j, ans = 0;
for(i=1;i<=m;i++){
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
for(i=0;i<n;i++){
if(!used[i]){
cnt++;
path.push_back(vl(0));
trav(i);
}
}
array<ll, 3> bp = {-1, -1, -1};
for(i=0;i<c;i++){
mx = -1, v1 = -1, v2 = -1;
dfs(path[i][0], 0, -1);
v1 = v2;
mx = -1;
dfs(v1, 0, -1);
caldis(v1, 0, -1, 0);caldis(v2, 0, -1, 1);
ll pc = path[i][0], pb = max(dis[pc][0], dis[pc][1]);
for(auto x: path[i]){
if(max(dis[x][0], dis[x][1]) > pb){
pc = x;
pb = max(dis[x][0], dis[x][1]);
}
}
ans = max(ans, pb);
if(pb > bp[0]){
bp[2] = bp[1];
bp[1] = bp[0];
bp[0] = pb;
}
else if(pb > bp[1]){
bp[2] = bp[1];
bp[1] = pb;
}
else if(pb > bp[2]){
bp[2] = pb;
}
}
ans = max(ans, bp[0] + bp[1] + L);
if(bp[3] != -1){
ans = max(ans, bp[1] + bp[2] + 2*L);
}
return ans;
}
Compilation message
dreaming.cpp: In function 'void trav(long long int)':
dreaming.cpp:22:17: error: 'egde' was not declared in this scope; did you mean 'edge'?
22 | dfs(egde.fi);
| ^~~~
| edge
dreaming.cpp:22:13: error: 'dfs' was not declared in this scope; did you mean 'dis'?
22 | dfs(egde.fi);
| ^~~
| dis
dreaming.cpp: In function 'void caldis(long long int, long long int, long long int, long long int)':
dreaming.cpp:41:24: error: too few arguments to function 'void dfs(long long int, long long int, long long int)'
41 | dfs(edge.fi);
| ^
dreaming.cpp:26:6: note: declared here
26 | void dfs(ll node, ll we, ll p){
| ^~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:59:15: error: 'c' was not declared in this scope
59 | for(i=0;i<c;i++){
| ^
dreaming.cpp:46:25: warning: unused variable 'j' [-Wunused-variable]
46 | ll n = N, m = M, i, j, ans = 0;
| ^
