oj.uz

Submission #91093

# Submission time Handle Problem Language Result Execution time Memory
91093 2018-12-26T08:47:21 Z YottaByte Shymbulak (IZhO14_shymbulak) C++14
0 / 100
 19 ms 844 KB 
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

const int N = 5001;

#define pb emplace_back
#define fr first
#define sc second
#define mk make_pair

int n, d[N], u[N];
int ans, mx, root;
vector < int > g[N], v;

void dij(int x, int curd = 1)
{
	priority_queue < pair < int, int > > pq;
	pq.push( mk( -curd, x ) );
	d[x] = curd;
	while(!pq.empty())
	{
		x = pq.top().sc;
		curd = -pq.top().fr;
		pq.pop();
		
		if(curd > d[x]) continue;
		for(int to : g[x])
		{
			if(d[to] == 0 || d[to] > curd + 1)
			{
				d[to] = curd + 1;
				pq.push( mk( -d[to], to ) );
			}
		}
	}
}

void dfs(int v, int dist = 0, int p = 0)
{
	u[v] = 1;
	
	if(dist == mx)
	{
		//printf("%d\n", v);
		ans++;
		return;
	}
	
	for(int to : g[v])
		if(d[to] - 1 == dist + 1)
			dfs(to, dist + 1, v);
}

main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		int a, b;
		scanf("%d", &a);
		scanf("%d", &b);
		
		g[a].pb(b);
		g[b].pb(a);
	}
	
	for(int i = 1; i <= n; i++)
	{
		memset(d, 0, sizeof(d)); dij(i);
		for(int j = 1; j <= n; j++)
		{
			if(mx < d[j] - 1)
			{
				root = i;
				mx = d[j] - 1;
			}
		}
	}
	
	memset(d, 0, sizeof(d)); dij(root);
	
	for(int i = 1; i <= n; i++)
	{
		if(d[i] - 1 == mx)
		{
			v.pb( i );
		}
	}
	
	dfs(root);
	
	printf("%d\n", ans);
}
/**

6
1 2
1 3
2 4
4 3
4 5
4 6

**/

Compilation message

shymbulak.cpp:57:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
shymbulak.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
shymbulak.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &b);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -