oj.uz

Submission #655965

# Submission time Handle Problem Language Result Execution time Memory
655965 2022-11-06T07:57:28 Z Shahrad Network (BOI15_net) C++17
0 / 100
 12 ms 23820 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;
#define endl '\n'
#define pb push_back
#define mk make_pair
#define sz size()
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define kill(x) return cout << x << endl, void();
#define int ll
typedef pair <int, int> pii;

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

const int N = 1e6 + 5;
const int MOD = 998244353, INF = 2e9, MOD2 = 1e9 + 7, sq = 350;

int st[N];
int t;
vector <int> adj[N];
vector <pii> vct;

void dfs (int v, int par)
{
	st[v] = t++;
	for (int u : adj[v])
		if (u != par)
			dfs (u, v);
}

void Solve ()
{
	int n, v, u;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		cin >> v >> u;
		v--, u--;
		adj[v].pb (u);
		adj[u].pb (v);
	}
	for (int i = 0; i < n; i++)
		if (adj[i].sz > 1)
			v = i;
	dfs (v, -1);
	for (int i = 0; i < n; i++)
		if (adj[i].sz == 1)
			vct.pb (mk (st[i], i));
	sort (all (vct));
	cout << (vct.sz + 1) / 2 << endl;
	if (vct.sz % 2)
		cout << vct.back ().S + 1 << ' ' << v + 1 << endl;
	for (int i = 0; i < vct.sz / 2; i++)
		cout << vct[i].S + 1 << ' ' << vct[i + vct.sz / 2].S + 1 << endl;
}

int32_t main ()
{
	ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
	int tt = 1;
//	cin >> tt;
	while (tt--)
		Solve ();
}

Compilation message

net.cpp: In function 'void Solve()':
net.cpp:59:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < vct.sz / 2; i++)
      |                  ~~^~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 12 ms 23820 KB Breaking single line is causing network to disconnect.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 12 ms 23820 KB Breaking single line is causing network to disconnect.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 12 ms 23820 KB Breaking single line is causing network to disconnect.
5 Halted 0 ms 0 KB -