Submission #17456

#	Time	Username	Problem	Language	Result	Execution time	Memory
17456		azecoder	Shymbulak (IZhO14_shymbulak)	C++98	50 / 100	752 ms	204788 KiB

shymbulak

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

#define MAXN 5005
#define intt int

using namespace std ;

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

vector < intt > edge[MAXN] ;

queue < intt > q ;

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] = 5005 ;
	
	for ( int i = 1 ; i <= n ; i ++ ) {
		
		q.push ( i ) ;
		
		d[i][i] = 0 ;
		
		t[i][i] = 1 ;
		
		while ( !q.empty ( ) ) {
			
			intt v = q.front () ;
			
			q.pop () ;
				
			for ( int j = 0 ; j < edge[v].size () ; j ++ ) {
				
				intt u = edge[v][j] ;
				
				if ( d[i][u] >= d[i][v] + 1 ) {
					
					if ( d[i][u] == d[i][v] + 1 ) t[i][u] += t[i][v] ;
					else {
						
						d[i][u] = d[i][v] + 1 ;
						
						t[i][u] += t[i][v] ;
						
						q.push ( u ) ;
							
					}
						
				}
					
			}
				
		}
		
		for ( int j = 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: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50