제출 #67251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67251		MatheusLealV	Network (BOI15_net)	C++17	0 / 100	15 ms	12136 KiB

net

#include <bits/stdc++.h>
#define N 500050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
 
int n, ponte, cnt, id[N], menor[N], root;
 
vector<int> grafo[N], leaf;
 
void dfs(int x, int p)
{
	menor[x] = x;

	for(auto v: grafo[x])
	{
		if(v == p) continue;

		dfs(v, x);

		menor[x] = min(menor[v], v);
	}
}
 
void dfs2(int x, int p)
{
	vector<pii> order;

	if(grafo[x].size() == 1) leaf.push_back(x);

	for(auto v: grafo[x])
	{
		if(v == p) continue;

		order.push_back({menor[v], v});
	}

	sort(order.begin(), order.end());

	for(auto v: order) dfs2(v.s, x);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
  
	cin>>n;
 
	for(int i = 1, a, b; i < n; i++)
	{
		cin>>a>>b;
 
		grafo[a].push_back(b);
 
		grafo[b].push_back(a);
	}
 
 	for(int i = 1; i <= n; i++)
 	{
 		if(grafo[i].size() <= 1) continue;

 		root = i;

 		break;
 	}

 	dfs(root, root);

 	dfs2(root, root);

 	cout<<(ceil(leaf.size()/2.0))<<"\n";

 	for(int i = 0, j = leaf.size() - 1; i < leaf.size() and j >= i; i++, j--)
 	{
 		if(i == j) cout<<leaf[i]<<" "<<leaf[i + 1]<<"\n";

 		else cout<<leaf[i]<<" "<<leaf[j]<<"\n";
 	}
}

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

net.cpp: In function 'int main()':
net.cpp:74:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0, j = leaf.size() - 1; i < leaf.size() and j >= i; i++, j--)
                                       ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37