oj.uz

Submission #91448

# Submission time Handle Problem Language Result Execution time Memory
91448 2018-12-27T13:45:00 Z YottaByte Shymbulak (IZhO14_shymbulak) C++14
50 / 100
 524 ms 1284 KB 
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

const int N = 5001;

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

vector < int > g[N];
int n, d[N], dist[N], c[N], par[N];

void bfs(int x)
{
	queue < int > q;
	q.push(x);
	c[x] = 1;
	dist[x] = 1;
	while(!q.empty())
	{
		x = q.front();
		d[dist[x] - 1] += c[x];
		q.pop();
		for(int to : g[x])
		{
			if(to == par[x]) 
				continue;
			if(c[to] == 0){
				dist[to] = dist[x] + 1;
				q.push(to);
				par[to] = x;
			}
			if(dist[to] > dist[x])
				c[to] += c[x];
		}
	}
}

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(c, 0, sizeof(c));
		memset(dist, 0, sizeof(dist));
		memset(par, 0, sizeof(par));
		bfs(i);
 	}
	for(int i = n; i >= 1; i --){
		if(d[i]){
			printf("%d", d[i] / 2);
			return 0;
		}
	}
}
/**

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

9
1 2
2 3
2 4
2 5
5 9
5 7
7 6
6 1
1 8

**/

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 688 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 2 ms 688 KB Output is correct
5 Correct 2 ms 688 KB Output is correct
6 Correct 2 ms 688 KB Output is correct
7 Correct 2 ms 688 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Correct 2 ms 704 KB Output is correct
10 Correct 2 ms 704 KB Output is correct
11 Correct 2 ms 704 KB Output is correct
12 Correct 2 ms 704 KB Output is correct
13 Correct 3 ms 704 KB Output is correct
14 Correct 6 ms 704 KB Output is correct
15 Correct 6 ms 704 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 720 KB Output is correct
2 Correct 9 ms 720 KB Output is correct
3 Correct 17 ms 740 KB Output is correct
4 Correct 16 ms 744 KB Output is correct
5 Correct 468 ms 1008 KB Output is correct
6 Correct 325 ms 1184 KB Output is correct
7 Correct 513 ms 1184 KB Output is correct
8 Correct 524 ms 1184 KB Output is correct
9 Correct 451 ms 1192 KB Output is correct
10 Correct 479 ms 1240 KB Output is correct

Subtask #3
0 / 50.0

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