oj.uz

Submission #876011

# Submission time Handle Problem Language Result Execution time Memory
876011 2023-11-21T05:20:55 Z vjudge1 Network (BOI15_net) C++17
0 / 100
 1 ms 2652 KB 
#include <bits/stdc++.h>
using namespace std;
bool seen[100005]={false};
vector<int> links[100005];
vector<int> roots;
int last=-1;
void dfs(int at){
	if(seen[at]){
		return;
	}
	seen[at]=true;
	if(links[at].size()==1){
		roots.push_back(at);
	}
	for(int to:links[at]){
		if(!seen[to]) dfs(to);
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=0; i<n-1; i++){
		int a,b;
		cin>>a>>b;
		links[a].push_back(b);
		links[b].push_back(a);
	}
	dfs(1);
	int total=roots.size()/2;
	vector<pair<int,int>> ans;
	if(roots.size()%2==1){
		ans.push_back({roots[0],roots[roots.size()-1]});
	}
	for(int i=0; i<total; i++){
		ans.push_back({roots[i],roots[i+total]});
	}
	cout<<total<<endl;
	for(int i=0; i<ans.size(); i++){
		cout<<ans[i].first<<' '<<ans[i].second<<endl;
	}
}

Compilation message

net.cpp: In function 'int main()':
net.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i=0; i<ans.size(); i++){
      |               ~^~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Incorrect 1 ms 2652 KB Invalid number of links.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Incorrect 1 ms 2652 KB Invalid number of links.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Incorrect 1 ms 2652 KB Invalid number of links.
5 Halted 0 ms 0 KB -