oj.uz

Submission #119011

# Submission time Handle Problem Language Result Execution time Memory
119011 2019-06-20T07:32:51 Z SOIVIEONE Network (BOI15_net) C++14
0 / 100
 19 ms 12672 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define T(a, b, c) make_pair(a, make_pair(b, c))
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 522222

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int h[N], l[N];
vi v[N];
void dfs(int u, int e)
{
	h[u] = h[e] + 1;
	for(auto it : v[u])
		if(it != e)
			dfs(it, u);
}

bool kk(int x, int y)
{
	return (h[x] < h[y]);
}

int main()
{
	int n;
	cin >> n;
	for(int i = 2; i <= n; i ++)
	{
		int x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	int mx = 0, root = 0;
	int cnt = 0;
	for(int i = 1; i <= n ;i ++)
	{
		if(mx < v[i].size())
		{
			mx = v[i].size();
			root = i;
		}
		if(v[i].size() == 1)
			l[++cnt] = i;
	}
	dfs(root, 0);
//	deb(root);
	sort(l + 1, l + cnt + 1, kk);
	vector<pii> ans;
	for(int i = 1; i <= cnt/2; i ++)
	{
		ans.pb(M(l[i], l[cnt-i+1]));
	}
	if(cnt & 1)
		ans.pb(M(l[cnt/2+1], l[1]));
	cout << ans.size() << '\n';
	for(auto it : ans)
		cout << it.F << ' ' << it.S << '\n';


	





	getchar();
	getchar();
	return 0;
	//ios::sync_with_stdio(false);
	//cin.tie(0);
}

Compilation message

net.cpp: In function 'int main()':
net.cpp:64:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(mx < v[i].size())
      ~~~^~~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12672 KB Output is correct
2 Correct 14 ms 12644 KB Output is correct
3 Correct 13 ms 12672 KB Output is correct
4 Correct 14 ms 12544 KB Output is correct
5 Correct 14 ms 12544 KB Output is correct
6 Correct 13 ms 12544 KB Output is correct
7 Correct 13 ms 12672 KB Output is correct
8 Correct 13 ms 12672 KB Output is correct
9 Correct 13 ms 12672 KB Output is correct
10 Correct 13 ms 12672 KB Output is correct
11 Correct 12 ms 12672 KB Output is correct
12 Correct 12 ms 12672 KB Output is correct
13 Correct 19 ms 12544 KB Output is correct
14 Correct 12 ms 12672 KB Output is correct
15 Incorrect 13 ms 12544 KB Breaking single line is causing network to disconnect.
16 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12672 KB Output is correct
2 Correct 14 ms 12644 KB Output is correct
3 Correct 13 ms 12672 KB Output is correct
4 Correct 14 ms 12544 KB Output is correct
5 Correct 14 ms 12544 KB Output is correct
6 Correct 13 ms 12544 KB Output is correct
7 Correct 13 ms 12672 KB Output is correct
8 Correct 13 ms 12672 KB Output is correct
9 Correct 13 ms 12672 KB Output is correct
10 Correct 13 ms 12672 KB Output is correct
11 Correct 12 ms 12672 KB Output is correct
12 Correct 12 ms 12672 KB Output is correct
13 Correct 19 ms 12544 KB Output is correct
14 Correct 12 ms 12672 KB Output is correct
15 Incorrect 13 ms 12544 KB Breaking single line is causing network to disconnect.
16 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12672 KB Output is correct
2 Correct 14 ms 12644 KB Output is correct
3 Correct 13 ms 12672 KB Output is correct
4 Correct 14 ms 12544 KB Output is correct
5 Correct 14 ms 12544 KB Output is correct
6 Correct 13 ms 12544 KB Output is correct
7 Correct 13 ms 12672 KB Output is correct
8 Correct 13 ms 12672 KB Output is correct
9 Correct 13 ms 12672 KB Output is correct
10 Correct 13 ms 12672 KB Output is correct
11 Correct 12 ms 12672 KB Output is correct
12 Correct 12 ms 12672 KB Output is correct
13 Correct 19 ms 12544 KB Output is correct
14 Correct 12 ms 12672 KB Output is correct
15 Incorrect 13 ms 12544 KB Breaking single line is causing network to disconnect.
16 Halted 0 ms 0 KB -