Submission #927562

#TimeUsernameProblemLanguageResultExecution timeMemory
927562CutebolDreaming (IOI13_dreaming)C++17
0 / 100
33 ms12892 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std ; #define pii pair <int , int> #define ff first #define ss second const int inf = 1e9 ; const int N = 1e5 + 5 ; template <class T> bool chmax( T& x , const T& y ){ bool f = 0 ; if ( x < y ) x = y , f = 1 ; return f ; } template <class T> bool chmin( T &x , const T &y ){ bool f = 0 ; if ( x > y ) x = y , f = 1 ; return f ; } bool vis[N] ; int d[N] , f[N] , sc[N] ; int mx , m , ind , r ; pii ans[N] ; vector <pii> g[N] ; vector <pii> vec ; void dfs ( int v , int s , int& m ){ vis[v] = 1 ; d[v] = s ; if ( mx <= d[v] ){ m = v ; mx = d[v] ; } for ( auto to : g[v] ) if ( !vis[to.ff] ) dfs(to.ff,s+to.ss,m) ; } void fir ( int v , int d , int& m ){ vis[v] = 0 ; f[v] = d ; if ( chmax ( mx , f[v] ) ) m = v ; for ( auto to : g[v] ) if ( vis[to.ff] ) fir(to.ff,d+to.ss,m) ; } void sec ( int v , int d , int& m ){ vis[v] = 1 ; sc[v] = d ; if ( max( f[v] , sc[v] ) < mx ){ mx = max ( f[v] , sc[v] ) ; m = v ; } for ( auto to : g[v] ) if ( !vis[to.ff] ) sec(to.ff,d+to.ss,m) ; } int travelTime(int n, int m, int l, int a[], int b[], int c[]) { for ( int i = 0 ; i < m ; i ++ ){ g[a[i]].push_back({b[i],c[i]}) ; g[b[i]].push_back({a[i],c[i]}) ; } for ( int i = 1 ; i <= n ; i ++ ){ if ( !vis[i] ){ mx = 0 ; dfs(i,0,m) ; mx = 0 ; fir(m,0,m) ; chmax ( r , f[m] ) ; mx = inf ; sec(m,0,m) ; vec.push_back({max(f[m],sc[m]),m}) ; } } vec.push_back({0,0}) ; vec.push_back({0,0}) ; vec.push_back({0,0}) ; sort ( vec.rbegin() , vec.rend() ) ; return max({ r, vec[0].ff + vec[1].ff + l , vec[1].ff + vec[2].ff + 2*l }) ; } /* signed main(){ int n , m , l , a[N] , b[N] , t[N] ; cin >> n >> m >> l ; for ( int i = 0 ; i < m ; i ++ ) cin >> a[i] >> b[i] >> t[i] ; cout << travelTime( n , m , l , a , b , t ) ; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...