제출 #91448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91448		YottaByte	관광지 (IZhO14_shymbulak)	C++14	50 / 100	524 ms	1284 KiB

shymbulak

#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

**/

컴파일 시 표준 에러 (stderr) 메시지

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