oj.uz

Submission #928210

# Submission time Handle Problem Language Result Execution time Memory
928210 2024-02-16T04:53:19 Z Cutebol Dreaming (IOI13_dreaming) C++17
18 / 100
 29 ms 12892 KB 
#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 , r ;
pii ans[N] ;
vector <pii> g[N] ;
vector <int> 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 ( mx <= f[v] ){
		m = v ; mx = f[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[]) {
	vec.clear() ; r = 0 ;
    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 = 0 ; 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])) ;
		}
	}
	if ( n == 1 ) return 0 ;
	if ( n == 2 ){
		if ( m == 1 ) return 0 ;
		return l ;
	} int ans = r ;
	sort ( vec.rbegin() , vec.rend() ) ;
	if ( vec.size() > 1 ) chmax ( ans , l+vec[0] + vec[1] ) ;
	if ( vec.size() > 2 ) chmax ( ans , 2*l+vec[1] + vec[2] ) ;
	return ans ;
}
/*
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 ) ;
}
//*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12892 KB Output is correct
2 Correct 29 ms 12792 KB Output is correct
3 Correct 20 ms 10168 KB Output is correct
4 Correct 6 ms 5724 KB Output is correct
5 Correct 4 ms 5212 KB Output is correct
6 Correct 9 ms 6232 KB Output is correct
7 Incorrect 2 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 2 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12892 KB Output is correct
2 Correct 29 ms 12792 KB Output is correct
3 Correct 20 ms 10168 KB Output is correct
4 Correct 6 ms 5724 KB Output is correct
5 Correct 4 ms 5212 KB Output is correct
6 Correct 9 ms 6232 KB Output is correct
7 Incorrect 2 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8160 KB Output is correct
2 Correct 13 ms 8112 KB Output is correct
3 Correct 14 ms 8100 KB Output is correct
4 Correct 13 ms 8156 KB Output is correct
5 Correct 13 ms 8168 KB Output is correct
6 Correct 14 ms 8672 KB Output is correct
7 Correct 19 ms 8284 KB Output is correct
8 Correct 13 ms 8028 KB Output is correct
9 Correct 14 ms 8056 KB Output is correct
10 Correct 13 ms 8284 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 4 ms 6308 KB Output is correct
13 Correct 4 ms 6360 KB Output is correct
14 Correct 4 ms 6360 KB Output is correct
15 Correct 4 ms 6400 KB Output is correct
16 Correct 4 ms 6360 KB Output is correct
17 Correct 4 ms 6356 KB Output is correct
18 Correct 4 ms 6360 KB Output is correct
19 Correct 5 ms 6360 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 4 ms 6360 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 2 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12892 KB Output is correct
2 Correct 29 ms 12792 KB Output is correct
3 Correct 20 ms 10168 KB Output is correct
4 Correct 6 ms 5724 KB Output is correct
5 Correct 4 ms 5212 KB Output is correct
6 Correct 9 ms 6232 KB Output is correct
7 Incorrect 2 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -