Submission #17455

#	Time	Username	Problem	Language	Result	Execution time	Memory
17455		azecoder	Shymbulak (IZhO14_shymbulak)	C++98	0 / 100	0 ms	262144 KiB

shymbulak

#include <iostream>
#include <vector>
#include <queue>

#define MAXN 5005
#define intt long long

using namespace std ;

intt n , d[MAXN][MAXN] , t[MAXN][MAXN] , ans , mx , used[MAXN] ;

vector < intt > edge[MAXN] ;

queue < intt > q ;

intt bfs ( intt s ) {
	
	d[s][s] = 0 ;
	
	t[s][s] = 1 ;
	
	q.push ( s ) ;
	
	while ( !q.empty () ) {
		
		intt v = q.front () ;
		
		q.pop () ;
		
		used[v] = 1 ;
		
		for ( int i = 0 ; i < edge[v].size () ; i ++ ) {
			
			intt u = edge[v][i] ; 
			
			if ( d[s][u] >= d[s][v] + 1 ) {
				
				if ( d[s][u] == d[s][v] + 1 ) t[s][u] += t[s][v] ;
				else {
					
					d[s][u] = d[s][v] + 1 ;
					
					t[s][u] = t[s][v] ;
					
					if ( !used[u] ) q.push ( u ) ;
					
					used[u] = 1 ;
						
				}
					
			}
				
		}
			
	}
	
	for ( int i = 1; i <= n ; i ++ ) used[i] = 0 ;
		
}

int main () {
	
	cin >> n ;
	
	for ( int i = 0 ; i < n ; i ++ ) {
		
		intt x , y ;
		
		cin >> x >> y ;
		
		edge[x].push_back ( y ) ;
		
		edge[y].push_back ( x ) ;
			
	}
	
	for ( int i = 1 ; i <= n ; i ++ ) 
		for ( int j = 1 ; j <= n ; j ++ ) d[i][j] = 4343434343 ;

	
	for ( int i = 1 ; i <= n ; i ++ ) bfs ( i ) ;
	
	for ( int i = 1 ; i <= n ; i ++ ) {
		
		for ( int j = i + 1 ; j <= n ; j ++ ) {
			
			mx = max ( mx , d[i][j] ) ;
				
		}
		
	}
	
	for ( int i = 1 ; i <= n ; i ++ ) {
		
		for ( int j = i + 1 ; j <= n ; j ++ ) {
			
			if ( d[i][j] == mx ) ans += t[i][j] ;
				
		}
			
	}
	
	cout << ans << endl ;
	
	return 0 ;
		
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50