#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5+2;
#define ff first
#define ss second
#define pb push_back
vector <int> ans, cur ;
int best = 0 ;
int vis[N];
vector <pair<int,int>> G[N] ;
int node = 0 ;
map <pair<int,int>, int > dis ;
void fnd ( int u, int p, int d, int flag ) {
cur.push_back ( u ) ;
vis[u] = 1;
for ( auto v:G[u] ) {
if ( v.ff == p ) continue ;
fnd ( v.ff, u, d + v.ss, flag¯ ) ;
}
if ( d >= best ) {
best = d;
if ( flag && u == node ) ans = cur ;
if ( !flag ) node = u ;
}
cur.pop_back() ;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for ( int i = 0 ; i < M ; ++i ) G[A[i]].pb ( make_pair (B[i], T[i]) ), G[B[i]].pb ( make_pair(A[i], T[i]) ), dis[make_pair(A[i], B[i])] = dis[make_pair(B[i],A[i])] = T[i] ;
vector <int> toAn ;
for ( int i = 0 ; i < N ; ++i ) {
if ( vis[i] ) continue;
best = 0 ;
fnd ( i, -1, 0,0 ) ;
best = 0 ;
fnd ( node, -1, 0,0 ) ;
fnd ( node,-1,0,1) ;
vector <int> diLeft, diRg ;
diLeft.push_back (0) ;
diRg.push_back (0) ;
int lft = 0, rg = 0 ;
for ( int j = 1 ; j < ans.size() ; ++j ) {
lft += dis [ make_pair(ans[j], ans[j-1]) ] ;
diLeft.push_back(lft) ;
}
int sz = ans.size() ;
for ( int j = sz-2 ; j >= 0 ; --j ) {
rg += dis[make_pair(ans[j], ans[j]+1)] ;
diRg.push_back (rg) ;
}
reverse ( diRg.begin(), diRg.end() ) ;
int an = INT_MAX ;
for ( int i = 0 ; i < ans.size() ; ++i ) {
an = min ( an, max (diRg[i], diLeft[i]) ) ;
toAn.push_back ( an );
}
}
sort ( toAn.begin(), toAn.end() ) ;
int mx = toAn.back() + L ;
toAn.pop_back() ;
mx += toAn.back() ;
int scP = toAn.back() + 2 * L ;
if ( toAn.size() == 0 ) return mx ;
toAn.pop_back() ;
scP += toAn.back() ;
return max ( scP, mx ) ;
}
Compilation message
dreaming.cpp:23:38: error: stray '\302' in program
fnd ( v.ff, u, d + v.ss, flag¯ ) ;
^
dreaming.cpp:23:39: error: stray '\257' in program
fnd ( v.ff, u, d + v.ss, flag¯ ) ;
^
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:47:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for ( int j = 1 ; j < ans.size() ; ++j ) {
~~^~~~~~~~~~~~
dreaming.cpp:58:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for ( int i = 0 ; i < ans.size() ; ++i ) {
~~^~~~~~~~~~~~
