oj.uz

Submission #91395

# Submission time Handle Problem Language Result Execution time Memory
91395 2018-12-27T10:44:38 Z YottaByte Shymbulak (IZhO14_shymbulak) C++14
0 / 100
 4 ms 2756 KB 
#include <stdio.h>
#include <string.h>
#include <iomanip>
using namespace std;

const int N = 501;

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

int g1[N][N], g[N][N];
int n, d[N][N];

void floyd()
{
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			for(int k = 1; k <= n; k++)
			{
				if(g[i][j] == g[i][k] + g[k][j] && k != j && i != k && i != j)
				{
					g1[i][j] += g1[i][k] * g1[k][j];
				}
				if(g[i][j] > g[i][k] + g[k][j] && k != j && i != k && i != j){
					g1[i][j] = g1[i][k] * g1[k][j];
					g[i][j] = g[i][k] + g[k][j];
				}
			}
}

main()
{
	memset(g, 0x3f3f3f3f, sizeof(g));
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		int a, b;
		scanf("%d", &a);
		scanf("%d", &b);
		
		g[a][b] = 1;
		g[b][a] = 1;
		
		g1[a][b] = 1;
		g1[b][a] = 1;
		
	
	}
	
	floyd();
	
	int mx = 0;
	for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
	if(i != j)
	mx = (mx < g[i][j]) ? g[i][j] : mx;
	
	int ans = 0;
	for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
	{
	if(g[i][j] == mx)
	{
	ans += g1[i][j];
	}
	}
	
	//for(int i = 1; i <= n; i++)
	//for(int j = 1; j <= n; j++)
	//if(j == n)printf("%d\n", g[i][j]);
	//else 			printf("%d ", g[i][j]);
	
	printf("%d\n", ans / 2);
}
/**

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

5
1 2
2 3
3 4
4 5
5 1

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

4
1 2
1 3
1 4
4 3

**/

Compilation message

shymbulak.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
shymbulak.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
shymbulak.cpp:41: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 Correct 3 ms 1272 KB Output is correct
2 Correct 2 ms 1424 KB Output is correct
3 Incorrect 2 ms 1496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 50.0

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