oj.uz

Submission #68557

# Submission time Handle Problem Language Result Execution time Memory
68557 2018-08-17T10:01:18 Z ege_eksi Shymbulak (IZhO14_shymbulak) C++14
50 / 100
 1500 ms 196976 KB 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<list>
#include<algorithm>
#include<queue>

using namespace std;

int n;
list<int> *adj;

pair<int,int> BFS(int src)
{
	int *d = new int[n];
	int *way = new int[n];
	
	for(int i = 0 ; i < n ; i++)
	{
		d[i] = -1;
		way[i] = 0;
	}
	
	d[src] = 0;
	way[src] = 1;
	
	queue< int > q;
	
	list<int>::iterator it;
	
	q.push(src);
	
	int x;
	
	while(!q.empty())
	{
		x = q.front();
		q.pop();
		
		for(it = adj[x].begin() ; it != adj[x].end() ; it++)
		{
			if(d[*it] == -1)
			{
				d[*it] = d[x]+1;
				way[*it] = way[x];
				
				q.push(*it);
			}
			
			else if(d[*it] != -1 && d[x]+1 == d[*it])
			{
				way[*it]++;
			}
			
		}
	}
	
	int maxi = -1 , occ = 0;
	
	for(int i = 0 ; i < n ; i++)
	{
		if(d[i] > maxi)
		{
			maxi = d[i];
			occ = way[i];
		}
		else if(d[i] == maxi)
		{
			occ += way[i];
		}
	}
	
	return make_pair(maxi , occ);
}

int main()
{
	scanf("%d",&n);
	
	adj = new list<int>[n];
	
	int x , y;
	
	for(int i = 0 ; i < n ; i++)
	{
		scanf("%d %d",&x , &y);
		
		x--;
		y--;
		
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	
	pair<int , int> *arr = new pair<int,int>[n];
	
	for(int i = 0 ; i < n ; i++)
	{
		arr[i] = BFS(i);
	}
	
	int maxi = 0 , occ = 0;
	
	for(int i = 0 ; i < n ; i++)
	{
		if(arr[i].first > maxi)
		{
			maxi = arr[i].first;
			occ = arr[i].second;
		}
		else if(arr[i].first == maxi)
		{
			occ += arr[i].second;
		}
	}
	
	printf("%d" , occ/2);
	
	return 0;
}

Compilation message

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
shymbulak.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x , &y);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 4 ms 728 KB Output is correct
5 Correct 2 ms 728 KB Output is correct
6 Correct 2 ms 728 KB Output is correct
7 Correct 3 ms 728 KB Output is correct
8 Correct 2 ms 728 KB Output is correct
9 Correct 3 ms 728 KB Output is correct
10 Correct 3 ms 728 KB Output is correct
11 Correct 2 ms 728 KB Output is correct
12 Correct 3 ms 728 KB Output is correct
13 Correct 2 ms 740 KB Output is correct
14 Correct 11 ms 2532 KB Output is correct
15 Correct 9 ms 2532 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4448 KB Output is correct
2 Correct 18 ms 5612 KB Output is correct
3 Correct 27 ms 8572 KB Output is correct
4 Correct 24 ms 8572 KB Output is correct
5 Correct 931 ms 181520 KB Output is correct
6 Correct 612 ms 196976 KB Output is correct
7 Correct 1066 ms 196976 KB Output is correct
8 Correct 1329 ms 196976 KB Output is correct
9 Correct 931 ms 196976 KB Output is correct
10 Correct 997 ms 196976 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1574 ms 196976 KB Time limit exceeded
2 Halted 0 ms 0 KB -