#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 ;
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 p ){
int v;
visited[u] = 1 ;
color[u] = c ;
for(pi pr : adj[u] ){
v = pr.fi ;
if( v!= p){
dfs4(v,u);
}
}
}
// 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]) ;
}
priority_queue<int> q;
// for(int i = 0 ; i < N ; i++ ){
// if( !visited[i]){
// Min= 1e9 ;
// Max = 0 ;
// dfs(i,-1);
// dfs1(i,-1);
// dfs0(i,-1) ;
// q.push(Max) ;
// }
//
for(int i = 0 ; i < N ; i++ )if(!visited[i])dfs4(i,-1) , c++ , Min[color[i]]=1e9;
for(int i = 0 ; i < N ; i++ ){
Max = 0 ;
dfs3(i,-1,0) ;
Min[color[i]] = min(
Min[color[i]] , Max);
}
for(int i = 0 ; i < N ; i++ )q.push(Min[i]) ;
Max = q.top() ; q.pop() ;
return L + q.top() + Max ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1070 ms |
11332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1070 ms |
11332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1070 ms |
11332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
6392 KB |
Output is correct |
| 2 |
Incorrect |
32 ms |
6412 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1070 ms |
11332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1070 ms |
11332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
