oj.uz

Submission #17455

# Submission time Handle Problem Language Result Execution time Memory
17455 2015-12-13T16:02:04 Z azecoder Shymbulak (IZhO14_shymbulak) C++
0 / 100
 0 ms 262144 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
2 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
3 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
4 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
5 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
6 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
7 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
8 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
9 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
10 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
11 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
12 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
13 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
14 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
15 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
2 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
3 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
4 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
5 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
6 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
7 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
8 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
9 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
10 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
2 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
3 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
4 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
5 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
6 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
7 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
8 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
9 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
10 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
11 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
12 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded