oj.uz

Submission #876012

# Submission time Handle Problem Language Result Execution time Memory
876012 2023-11-21T05:21:55 Z vjudge1 Network (BOI15_net) C++17
63 / 100
 4 ms 5212 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;
	for(int i=0; i<total; i++){
		ans.push_back({roots[i],roots[i+total]});
	}
	if(roots.size()%2==1){
		ans.push_back({roots[0],roots[roots.size()-1]});
		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:39: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]
   39 |  for(int i=0; i<ans.size(); i++){
      |               ~^~~~~~~~~~~

Subtask #1
18.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 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct

Subtask #2
45.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 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 3 ms 2652 KB Output is correct
23 Correct 4 ms 2908 KB Output is correct
24 Correct 3 ms 2652 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 2 ms 2652 KB Output is correct
27 Correct 2 ms 2652 KB Output is correct
28 Correct 2 ms 2652 KB Output is correct
29 Correct 2 ms 2652 KB Output is correct
30 Correct 1 ms 2648 KB Output is correct
31 Correct 2 ms 2652 KB Output is correct
32 Correct 1 ms 2648 KB Output is correct
33 Correct 1 ms 2652 KB Output is correct
34 Correct 1 ms 2652 KB Output is correct
35 Correct 1 ms 2652 KB Output is correct
36 Correct 1 ms 2648 KB Output is correct
37 Correct 1 ms 2652 KB Output is correct
38 Correct 1 ms 2652 KB Output is correct
39 Correct 1 ms 2652 KB Output is correct
40 Correct 1 ms 2652 KB Output is correct
41 Correct 1 ms 2652 KB Output is correct
42 Correct 2 ms 2652 KB Output is correct
43 Correct 2 ms 2648 KB Output is correct
44 Correct 1 ms 2848 KB Output is correct
45 Correct 1 ms 2652 KB Output is correct
46 Correct 1 ms 2648 KB Output is correct
47 Correct 1 ms 2648 KB Output is correct
48 Correct 1 ms 2648 KB Output is correct
49 Correct 2 ms 2652 KB Output is correct
50 Correct 1 ms 2648 KB Output is correct
51 Correct 1 ms 2652 KB Output is correct
52 Correct 1 ms 2652 KB Output is correct
53 Correct 1 ms 2652 KB Output is correct
54 Correct 1 ms 2652 KB Output is correct
55 Correct 1 ms 2648 KB Output is correct
56 Correct 1 ms 2668 KB Output is correct
57 Correct 1 ms 2660 KB Output is correct
58 Correct 3 ms 2904 KB Output is correct

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 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 3 ms 2652 KB Output is correct
23 Correct 4 ms 2908 KB Output is correct
24 Correct 3 ms 2652 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 2 ms 2652 KB Output is correct
27 Correct 2 ms 2652 KB Output is correct
28 Correct 2 ms 2652 KB Output is correct
29 Correct 2 ms 2652 KB Output is correct
30 Correct 1 ms 2648 KB Output is correct
31 Correct 2 ms 2652 KB Output is correct
32 Correct 1 ms 2648 KB Output is correct
33 Correct 1 ms 2652 KB Output is correct
34 Correct 1 ms 2652 KB Output is correct
35 Correct 1 ms 2652 KB Output is correct
36 Correct 1 ms 2648 KB Output is correct
37 Correct 1 ms 2652 KB Output is correct
38 Correct 1 ms 2652 KB Output is correct
39 Correct 1 ms 2652 KB Output is correct
40 Correct 1 ms 2652 KB Output is correct
41 Correct 1 ms 2652 KB Output is correct
42 Correct 2 ms 2652 KB Output is correct
43 Correct 2 ms 2648 KB Output is correct
44 Correct 1 ms 2848 KB Output is correct
45 Correct 1 ms 2652 KB Output is correct
46 Correct 1 ms 2648 KB Output is correct
47 Correct 1 ms 2648 KB Output is correct
48 Correct 1 ms 2648 KB Output is correct
49 Correct 2 ms 2652 KB Output is correct
50 Correct 1 ms 2648 KB Output is correct
51 Correct 1 ms 2652 KB Output is correct
52 Correct 1 ms 2652 KB Output is correct
53 Correct 1 ms 2652 KB Output is correct
54 Correct 1 ms 2652 KB Output is correct
55 Correct 1 ms 2648 KB Output is correct
56 Correct 1 ms 2668 KB Output is correct
57 Correct 1 ms 2660 KB Output is correct
58 Correct 3 ms 2904 KB Output is correct
59 Runtime error 2 ms 5212 KB Execution killed with signal 11
60 Halted 0 ms 0 KB -