oj.uz

Submission #17456

# Submission time Handle Problem Language Result Execution time Memory
17456 2015-12-13T16:09:21 Z azecoder Shymbulak (IZhO14_shymbulak) C++
50 / 100
 752 ms 204788 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 197560 KB Output is correct
2 Correct 0 ms 197560 KB Output is correct
3 Correct 0 ms 197560 KB Output is correct
4 Correct 0 ms 197560 KB Output is correct
5 Correct 0 ms 197560 KB Output is correct
6 Correct 0 ms 197560 KB Output is correct
7 Correct 0 ms 197560 KB Output is correct
8 Correct 0 ms 197560 KB Output is correct
9 Correct 0 ms 197560 KB Output is correct
10 Correct 0 ms 197560 KB Output is correct
11 Correct 0 ms 197560 KB Output is correct
12 Correct 0 ms 197560 KB Output is correct
13 Correct 0 ms 197560 KB Output is correct
14 Correct 0 ms 197560 KB Output is correct
15 Correct 4 ms 197560 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 197560 KB Output is correct
2 Correct 8 ms 197560 KB Output is correct
3 Correct 26 ms 197560 KB Output is correct
4 Correct 29 ms 197560 KB Output is correct
5 Correct 683 ms 197692 KB Output is correct
6 Correct 441 ms 197692 KB Output is correct
7 Correct 752 ms 197692 KB Output is correct
8 Correct 739 ms 197692 KB Output is correct
9 Correct 669 ms 197692 KB Output is correct
10 Correct 721 ms 197692 KB Output is correct

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 361 ms 200460 KB Program hung waiting for input
2 Runtime error 383 ms 200856 KB SIGSEGV Segmentation fault
3 Runtime error 386 ms 200592 KB SIGSEGV Segmentation fault
4 Runtime error 371 ms 200724 KB SIGSEGV Segmentation fault
5 Runtime error 370 ms 200724 KB SIGSEGV Segmentation fault
6 Runtime error 735 ms 203100 KB SIGSEGV Segmentation fault
7 Runtime error 543 ms 202176 KB SIGSEGV Segmentation fault
8 Runtime error 724 ms 203892 KB SIGSEGV Segmentation fault
9 Runtime error 729 ms 203892 KB SIGSEGV Segmentation fault
10 Runtime error 750 ms 204156 KB SIGSEGV Segmentation fault
11 Runtime error 684 ms 204524 KB SIGSEGV Segmentation fault
12 Runtime error 737 ms 204788 KB SIGSEGV Segmentation fault