Submission #394597

#	Time	Username	Problem	Language	Result	Execution time	Memory
394597		AriaH	Network (BOI15_net)	C++11	100 / 100	589 ms	66548 KiB

net

/** vaziat sorati ghermeze **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int n, ptr, St[N];

vector < int > leaf, G[N];

void dfs(int v, int P = 0)
{
	St[v] = ++ ptr;
	for(auto u : G[v])
	{
		if(u == P) continue;
		dfs(u, v);
	}
}

bool cmp(int i, int j)
{
	return St[i] < St[j];
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i < n ;i ++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int root = 1;
	for(int i = 1; i <= n; i ++)
	{
		if(SZ(G[i]) > 1) root = i;
		if(SZ(G[i]) == 1) leaf.push_back(i);
	}
	dfs(root);
	/*for(int i = 1; i <= n; i ++)
	{
		printf("%d ", St[i]);
	}
	printf("\n");*/
	/*for(auto x : leaf)
	{
		printf("%d ", x);
	}
	printf("\n");*/
	sort(all(leaf), cmp);
	int cu = SZ(leaf) >> 1;
	printf("%d\n", SZ(leaf) - cu);
	for(int i = 0; i < SZ(leaf) - cu; i ++)
	{
		printf("%d %d\n", leaf[i], leaf[i + cu]);
	}
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
net.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

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