oj.uz

Submission #311447

# Submission time Handle Problem Language Result Execution time Memory
311447 2020-10-10T08:37:59 Z sofapuden Network (BOI15_net) C++14
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> v;
vector<int> o;
vector<int> lea;

void dfs(int x, int p){
	for(int y : v[x]){
		if(y == p)continue;
		dfs(y,x);
	}
	o.push_back(x);
}

int main(){
	int n; cin >> n;
	v.resize(n);
	for(int i = 0; i < n-1; ++i){
		int a, b; cin >> a >> b;
		a--, b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(0,0);
	for(int x : o){
		if(v[x].size() == 1)lea.push_back(x);
	}
	int ln = lea.size();
	bool ok = 0;
	cout << (ln+1)/2 << "\n";
	if(lea[ln-1] == 0){
		lea.pop_back();
		ln--;
		cout << 1 << " " << lea[ln/2]+1 << "\n";
		ok = 1;
	}
	for(int i = 0; i < ln/2; ++i){
		cout << lea[i]+1 << " " << lea[ln-1-i]+1 << "\n";
	}
	if((ln&1) && !ok){
		cout << lea[0]+1 << " " << lea[ln/2]+1 << "\n";
	}
		
}

Subtask #1
0 / 18.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 37.0

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