Submission #47126

#	Time	Username	Problem	Language	Result	Execution time	Memory
47126		MatheusLealV	Network (BOI15_net)	C++17	63 / 100	2049 ms	52396 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, dfsnum[N], dfslow[N], pai[N], ptr;

vector<int> grafo[N], leaf;

inline void dfs(int x)
{
	dfsnum[x] = dfslow[x] = ++cnt;
 
	for(int i = 0; i< grafo[x].size(); i++)
	{
		int v = grafo[x][i];
 
		if(!dfsnum[v])
		{
			pai[v] = x;
 
			dfs(v);
 
			if(dfslow[v] > dfsnum[x]) ponte ++;
 
			dfslow[x] = min(dfslow[v], dfslow[x]);
		}
 
		else if(v != pai[x]) dfslow[x] = min(dfsnum[v], dfslow[x]);
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	srand(42);

	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) leaf.push_back(i);

	else ptr = i;

	if(leaf.size() % 2) leaf.push_back(ptr);

	for(int c = 0; c < 50; c++)
	{
		memset(dfsnum, 0, sizeof dfsnum);

		memset(dfslow, 0, sizeof dfslow);

		ponte = cnt = 0;

	  	random_shuffle(leaf.begin(), leaf.end());

	    for(int i = 0; i< leaf.size(); i += 2)
	    {
	      	int a = leaf[i], b = leaf[i + 1];

	     	grafo[a].push_back(b);

	      	grafo[b].push_back(a);
	    }	

	    dfs(1);

	    if(!ponte)
	    {
	    	cout<<(leaf.size() + 1)/2<<"\n";

		    for(int i = 0; i< leaf.size(); i += 2)
		    {
		      	int a = leaf[i], b = leaf[i + 1];

		     	cout<<a<<" "<<b<<"\n";
		    }	

		    break;
	  	}

	    for(int i = 0; i< leaf.size(); i += 2)
	    {
	     	int a = leaf[i], b = leaf[i + 1];

	       	grafo[a].pop_back();

	      	grafo[b].pop_back();
	    }    
	}
}

Compilation message (stderr)

net.cpp: In function 'void dfs(int)':
net.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i< grafo[x].size(); i++)
                 ~^~~~~~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0; i< leaf.size(); i += 2)
                     ~^~~~~~~~~~~~~
net.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i< leaf.size(); i += 2)
                      ~^~~~~~~~~~~~~
net.cpp:93:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0; i< leaf.size(); i += 2)
                     ~^~~~~~~~~~~~~

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