oj.uz

Submission #655939

# Submission time Handle Problem Language Result Execution time Memory
655939 2022-11-06T06:58:17 Z aebov Network (BOI15_net) C++17
0 / 100
 6 ms 11988 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<utility>
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

const int N = (int)5e5 + 5;
int n , u, v, ind[N], _id = 0, root = 1;
vector<int> leafs;
vector<pii> ret;
vector<int> adj[N]; 

void dfs(int v,int p){
	ind[v] = _id ++;
	for(auto u : adj[v])if(u != p)dfs(u , v);
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i < n ; i ++){
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(int i = 1; i <= n; i ++)if(adj[i].size() > 1)root = i;
	dfs(root, root);
	for(int i = 1; i <= n; i ++){
		if(adj[i].size() == 1)ret.pb({ind[i], i});
	}
	sort(ret.begin(), ret.end());
	int sz= ret.size();
	cout << ((sz + 1) >> 1);
	for(int i = 0; i < sz/2; i ++)	cout << ret[i].S << " " << ret[i + (sz+1)/2].S << endl;
	if(sz&1) cout << ret[sz/2].S << " " << root << endl;
	exit(0);
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11988 KB Invalid number of links.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11988 KB Invalid number of links.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11988 KB Invalid number of links.
2 Halted 0 ms 0 KB -