#include "dreaming.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
vector <ii> adj[100010];
bool mk[100010];
int maxDist, ennd,ans;
ii p[100010];
vector <int> r;
void dfs(int v, int par, int len, int flag)
{
if(flag)
mk[v] = true;
if(len > maxDist)
{
maxDist = len;
ennd = v;
}
for(int i = 0; i < adj[v].size(); i++)
{
int u = adj[v][i].first;
if(u == par) continue;
int weight = adj[v][i].second;
if(flag)
p[u] = ii(v,weight);
dfs(u,v,len+weight,flag);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < M; i++)
{
adj[A[i]].pb(ii(B[i],T[i]));
adj[B[i]].pb(ii(A[i],T[i]));
}
for(int i = 0; i < N; i++)
{
if(mk[i]) continue;
maxDist = -1;
dfs(i,i,0,0);
maxDist = -1;
int first = ennd;
dfs(first,first,0,1);
ans = max(ans,maxDist);
int second = ennd;
int halfdiam = maxDist / 2;
int radius = 0;
for(int ver = second; ver != first; ver = p[ver].first)
{
if(radius + p[ver].second > halfdiam)
{
radius = max(radius,maxDist - radius);
break;
}
radius += p[ver].second;
}
r.pb(radius);
}
sort(r.begin(),r.end());
reverse(r.begin(),r.end());
if (r.size() > 1) ans = max(ans, R[0] + R[1] + L);
if (r.size() > 2) ans = max(ans, R[1] + R[2] + L + L);
return ans;
}
Compilation message
dreaming.cpp: In function 'void dfs(int, int, int, int)':
dreaming.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[v].size(); i++)
~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:69:36: error: 'R' was not declared in this scope
if (r.size() > 1) ans = max(ans, R[0] + R[1] + L);
^
dreaming.cpp:70:35: error: 'R' was not declared in this scope
if (r.size() > 2) ans = max(ans, R[1] + R[2] + L + L);
^
