Submission #68557

#	Time	Username	Problem	Language	Result	Execution time	Memory
68557		ege_eksi	Shymbulak (IZhO14_shymbulak)	C++14	50 / 100	1574 ms	196976 KiB

shymbulak

#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 (stderr)

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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50