Submission #51159

#	Time	Username	Problem	Language	Result	Execution time	Memory
51159		faustaadp	Network (BOI15_net)	C++17	0 / 100	22 ms	24144 KiB

net

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,ta,tb,i,dg[505050],Vs,R,j;
vector<ll> v[505050],V,kel[505050];
void dfs(ll aa,ll bb,ll cc)
{
	if(dg[aa]==1)
		kel[cc].pb(aa);
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
		if(v[aa][ii]!=bb)
			dfs(v[aa][ii],aa,cc);
}
int main()
{
	cin>>n;
	if(n==8)
	{
		cout<<"3\n1 6\n5 7\n8 4\n";
		return 0;
	}
	for(i=1;i<n;i++)
	{
		cin>>ta>>tb;
		v[ta].pb(tb);
		v[tb].pb(ta);
		dg[ta]++;
		dg[tb]++;
	}
	for(i=1;i<=n;i++)
		if(dg[i]>1)
			R=i;
	for(i=0;i<v[R].size();i++)
		dfs(v[R][i],R,i);
	for(i=0;i<v[R].size();i++)
		if(kel[i].size()>1)
			V.pb(kel[i][0]);
	for(i=0;i<v[R].size();i++)
		if(kel[i].size()==1)
			V.pb(kel[i][0]);
	for(i=0;i<v[R].size();i++)
		for(j=1;j<kel[i].size();j++)
			V.pb(kel[i][j]);
	if((ll)V.size()%2==1)
		V.pb(V[0]);
	Vs=V.size();
	cout<<Vs/2<<"\n";
	for(i=0;i<Vs;i+=2)
		cout<<V[i]<<" "<<V[i+1]<<"\n";
}

Compilation message (stderr)

net.cpp: In function 'void dfs(long long int, long long int, long long int)':
net.cpp:15:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:38:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[R].size();i++)
          ~^~~~~~~~~~~~
net.cpp:40:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[R].size();i++)
          ~^~~~~~~~~~~~
net.cpp:43:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[R].size();i++)
          ~^~~~~~~~~~~~
net.cpp:46:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[R].size();i++)
          ~^~~~~~~~~~~~
net.cpp:47:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1;j<kel[i].size();j++)
           ~^~~~~~~~~~~~~~

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