oj.uz

Submission #239825

# Submission time Handle Problem Language Result Execution time Memory
239825 2020-06-17T10:57:23 Z kshitij_sodani Network (BOI15_net) C++17
0 / 100
 12 ms 12032 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second



int n;
vector<int> adj[500001];
vector<int> kk;
void dfs(int no,int par=-1){

	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no);
		}
	}
	if(adj[no].size()==1){
		kk.pb(no);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n-1;i++){
		int aa,bb;
		cin>>aa>>bb;
		adj[aa-1].pb(bb-1);
		adj[bb-1].pb(aa-1);

	}
	int r=0;
	for(int i=0;i<n;i++){
		if(adj[i].size()>1){
			r=i;
		}
	}
	dfs(r);
	cout<<((kk.size()+1)/2)<<endl;
	for(int i=0;i<kk.size()/2;i++){
		cout<<kk[i]+1<<" "<<kk[kk.size()-i-1]+1<<endl;
	}
	if(kk.size()%2==1){
		cout<<kk[kk.size()/2]+1<<" "<<r<<endl;
	}


	return 0;
}

Compilation message

net.cpp: In function 'int main()':
net.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<kk.size()/2;i++){
              ~^~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12032 KB Output is correct
2 Incorrect 12 ms 12032 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 12 ms 12032 KB Output is correct
2 Incorrect 12 ms 12032 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 12 ms 12032 KB Output is correct
2 Incorrect 12 ms 12032 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -