Submission #108708

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
108708	2019-05-01T06:10:33 Z	Mahdi_Jfri	Network (BOI15_net)	C++14	0 / 100	15 ms	12160 KB

net

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 5e5 + 20;

vector<int> adj[maxn] , tmp;

void dfs(int v , int p = -1)
{
	if((int)adj[v].size() == 1)
		tmp.pb(v);
	for(auto u : adj[v])
		if(u != p)
			dfs(u , v);
}

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

	int n;
	cin >> n;

	for(int i = 0; i < n - 1; i++)
	{
		int a , b;
		cin >> a >> b;
		a-- , b--;

		adj[a].pb(b);
		adj[b].pb(a);
	}

	int root = -1;
	for(int i = 0; i < n; i++)
		if((int)adj[i].size() != 1)
		{
			root = i;
			dfs(i);
			break;
		}

	int k = tmp.size();
	cout << (k + 1) / 2 << endl;

	if(k & 1)
		cout << root + 1 << " " << tmp.back() + 1 << endl , tmp.pop_back();

	for(int i = 0; i < k / 2; i++)
		cout << tmp[i] + 1 << " " << tmp[i + k / 2] + 1 << endl;
}

Subtask #1

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	12032 KB	Output is correct
2	Correct	13 ms	12160 KB	Output is correct
3	Correct	14 ms	12032 KB	Output is correct
4	Correct	13 ms	12032 KB	Output is correct
5	Correct	14 ms	12032 KB	Output is correct
6	Correct	15 ms	12032 KB	Output is correct
7	Incorrect	14 ms	12160 KB	Breaking single line is causing network to disconnect.
8	Halted	0 ms	0 KB	-

Subtask #2

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	12032 KB	Output is correct
2	Correct	13 ms	12160 KB	Output is correct
3	Correct	14 ms	12032 KB	Output is correct
4	Correct	13 ms	12032 KB	Output is correct
5	Correct	14 ms	12032 KB	Output is correct
6	Correct	15 ms	12032 KB	Output is correct
7	Incorrect	14 ms	12160 KB	Breaking single line is causing network to disconnect.
8	Halted	0 ms	0 KB	-

Subtask #3

0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	12032 KB	Output is correct
2	Correct	13 ms	12160 KB	Output is correct
3	Correct	14 ms	12032 KB	Output is correct
4	Correct	13 ms	12032 KB	Output is correct
5	Correct	14 ms	12032 KB	Output is correct
6	Correct	15 ms	12032 KB	Output is correct
7	Incorrect	14 ms	12160 KB	Breaking single line is causing network to disconnect.
8	Halted	0 ms	0 KB	-