| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 128910 | youssefbou62 | Dreaming (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.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( !visited[v]) {
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[]){
vector<int> ans ;
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,-1) ;
c++ ;
}
Min[i]=1e9;
}
for(int i = 0 ; i < N ; i++ ){
Max = 0 ;
dfs3(i,-1,0) ;
Min[color[i]] =min( Min[color[i]] , Max );
}
int a =0, b =0;
for(int i = 0 ; i < N ; i++ ){
if( Min[i]!= 1e9 ){
max2(a,b,Min[i]) ;
}
}
// sort(all(ans)) ;
// int ans1= 0 ;
// if(!ans.empty())ans1+=ans.back() , ans.pop_back() ;
if( N == 1 )return a;
// if(!ans.empty())ans1+=ans.back() , ans.pop_back() ;
// // cout <<
return (a+b+L) ;
}
// 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;
// }