oj.uz

Submission #67256

# Submission time Handle Problem Language Result Execution time Memory
67256 2018-08-13T17:39:31 Z MatheusLealV Network (BOI15_net) C++17
0 / 100
 12 ms 12136 KB 
#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[x], menor[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<<root<<"\n";

 	for(auto x: leaf) cout<<x<<" ";

 	cout<<"\n";*/

 	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";
 	}
}

Compilation message

net.cpp: In function 'int main()':
net.cpp:80: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.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12024 KB Output is correct
2 Incorrect 12 ms 12136 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12024 KB Output is correct
2 Incorrect 12 ms 12136 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12024 KB Output is correct
2 Incorrect 12 ms 12136 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -