Submission #556561

#	Time	Username	Problem	Language	Result	Execution time	Memory
556561		Hanksburger	Network (BOI15_net)	C++17	0 / 100	8 ms	11988 KiB

net

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > ans;
vector<int> adj[500005];
int dfs(int u, int p)
{
	vector<int> vec;
	for (int i=0; i<adj[u].size(); i++)
	{
		int v=adj[u][i];
		if (v!=p)
			vec.push_back(dfs(v, u));
	}
	int sz=vec.size();
	if (!sz)
		return u;
	if (sz==1)
		return vec[0];
	for (int i=1; i<sz; i+=2)
		ans.push_back({vec[i-1], vec[i]});
	if (sz&1)
		ans.push_back({vec[sz-2], vec[sz-1]});
	return vec[sz-1];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, root;
	cin >> n;
	for (int i=1; i<n; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i=1; i<=n; i++)
	{
		if (adj[i].size()>=2)
		{
			root=i;
			break;
		}
	}
	dfs(root, 0);
	cout << ans.size() << '\n';
	for (int i=0; i<ans.size(); i++)
		cout << ans[i].first << ' ' << ans[i].second << '\n';
	return 0;
}

Compilation message (stderr)

net.cpp: In function 'int dfs(int, int)':
net.cpp:8:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for (int i=0; i<adj[u].size(); i++)
      |                ~^~~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i=0; i<ans.size(); i++)
      |                ~^~~~~~~~~~~
net.cpp:47:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |  dfs(root, 0);
      |  ~~~^~~~~~~~~

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