#include <bits/stdc++.h>
#include <dreaming.h>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll ;
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef priority_queue< int, vector <int> , greater<int> > spq;
const int NN = 1e5+5 ;
vpi adj[NN] ;
int dp1[NN],dp2 [NN] , color[NN];
bool visited[NN] ;
int Min[NN], Max, c ,a,b ;
void dfs3(int u , int p , int d ){
int v , w;
Max = max ( Max , d ) ;
for(pi pr : adj[u] ){
v = pr.fi ;
w = pr.se ;
if( v!= p){
dfs3(v,u,d+w);
}
}
}
void dfs4(int u ){
int v;
visited[u] = 1 ;
color[u] = c ;
for(pi pr : adj[u] ){
v = pr.fi ;
if( !visited[v]) {
dfs4(v);
}
}
}
void max2(int& a , int& b , int x ){
if( x < b) return ;
if( x > a ){
b = a ;
a = x ;
return ;
}
if( x > b && x < a ){
b = x ;
}
}
/*
void dfs(int u , int p){
int v , w;
visited[u] = 1 ;
for(pi pr : adj[u] ){
v = pr.fi ;
w = pr.se ;
if( v != p ){
dfs(v,u) ;
max2(dp1[u],dp2[u],w+dp1[v]);
}
}
}
void dfs0(int u , int p ){
// cout << u << " " << dp1[u] << " " << dp2[u]<<endl ;
for(pi v : adj[u]){
if( v.fi != p )
dfs0(v.fi,u) ;
}
}
void dfs1(int u , int p ){
int w , v ;
for(pi pr : adj[u] ){
v = pr.fi ;
w = pr.se ;
if( v != p ){
if( dp1[u] != dp1[v]+w){
dp1[v] = max(dp1[u]+w,dp1[v]) ;
}if( dp1[u] != dp2[v]+w){
dp2[v] = max(dp1[u]+w,dp2[v]) ;
}
dfs1(v,u) ;
}
}
Min = min(Min,dp1[u]) ;
}
*/
void edge(int u , int v , int w ){
adj[u].pb({v,w}) ;
}
int travelTime(int N,int M,int L ,int A[],int B[],int T[]){
for(int i = 0 ; i < M ; i++ ){
edge(A[i],B[i],T[i]) ;
edge(B[i],A[i],T[i]) ;
}
for(int i = 0 ; i < N ; i++ ){
if(!visited[i]){
dfs4(i) ;
c++ ;
}
Min[i]=1e9;
}
int ans = 0 ;
for(int i = 0 ; i < N ; i++ ){
Max = 0 ; dfs3(i,-1,0) ;
ans = max (Max,ans) ;
Min[color[i]] =min( Min[color[i]] , Max );
}
for(int i = 0 ; i < c ; i++ ){
if( Min[i]!= 1e9 ){
max2(a,b,Min[i]) ;
}
}
// cout << Min[0]<<" " <<Min[1] << endl ;
// cout << a << " " << b << endl;
if( N == 1 )return a;
ans = max ( ans , a + b + L ) ;
return ans ;
}
// int main(){
// ifstream cin("in.in");
// int n,m,l;
// cin >>n>>m >>l;
// int a[m],b[m],t[m] ;
// for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>t[i] ;
// cout << travelTime(n,m,l,a,b,t) << endl;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
12920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
12920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
12920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
6304 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
6228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
12920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
12920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
