# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
298510 |
2020-09-13T03:38:11 Z |
jbroeksteeg |
Network (BOI15_net) |
C++14 |
|
853 ms |
47728 KB |
#include <iostream>
#include <climits>
#include <numeric>
#include <cassert>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <vector>
#include <array>
#include <memory>
#define IN(a,b) (a.find(b) != a.end())
#define p(a,b) make_pair(a,b)
#define readVec(a) for (int __i = 0; __i<(int)a.size();__i++){cin>>a[__i];}
// jimjam
template<typename T>
void pMin(T &a, T b) {if (b<a){a=b;}}
template<typename T>
void pMax(T &a, T b) {if (b>a){a=b;}}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& c);
template<typename A, typename B>
std::ostream& operator<<(std::ostream& os, const std::pair<A,B>& c) {std::cout << "(" << c.first << ", " << c.second << ")";return os;}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& c) {
if (c.size() == 0) {os << "{}"; return os;}
os << "{" << c[0];
for (int i = 1; i < (int)c.size(); i++) {os <<", "<<c[i];}
os << "}";
return os;
}
const int inf = 2e9;
#define MAXN 500001
using namespace std;
vector<int> adj[MAXN];
vector<int> leaves;
void dfs(int c, int p=-1) {
if (adj[c].size()==1) {
leaves.push_back(c);
}
for (int i: adj[c]) {
if (i!=p) {
dfs(i,c);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
for (int i = 0; i < n-1; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if (adj[i].size()>1) {
dfs(i);
break;
}
}
// cout << leaves.size()/2 + leaves.size()%2 << "\n";
int cnt=0;
while (cnt<leaves.size()) {
if (cnt+1==leaves.size()) {
// cout << leaves[cnt] << " 1\n";
cnt++;
} else {
// cout << leaves[cnt] << " " << leaves[cnt+1] << "\n";
cnt+=2;
}
}
cout << leaves.size()/2 + leaves.size()%2 << endl;
for (int i = 0; i < leaves.size()/2+leaves.size()%2; i++) {
cout << leaves[i] << " " << leaves[i + leaves.size()/2] << endl;
//if (other<i) break;
}
return 0;
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:75:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | while (cnt<leaves.size()) {
| ~~~^~~~~~~~~~~~~~
net.cpp:76:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if (cnt+1==leaves.size()) {
| ~~~~~^~~~~~~~~~~~~~~
net.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 0; i < leaves.size()/2+leaves.size()%2; i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12032 KB |
Output is correct |
2 |
Correct |
8 ms |
12032 KB |
Output is correct |
3 |
Correct |
8 ms |
12160 KB |
Output is correct |
4 |
Correct |
8 ms |
12032 KB |
Output is correct |
5 |
Correct |
8 ms |
12032 KB |
Output is correct |
6 |
Correct |
8 ms |
12032 KB |
Output is correct |
7 |
Correct |
8 ms |
12032 KB |
Output is correct |
8 |
Correct |
8 ms |
12032 KB |
Output is correct |
9 |
Correct |
8 ms |
12032 KB |
Output is correct |
10 |
Correct |
8 ms |
12032 KB |
Output is correct |
11 |
Correct |
8 ms |
12032 KB |
Output is correct |
12 |
Correct |
8 ms |
12032 KB |
Output is correct |
13 |
Correct |
9 ms |
12032 KB |
Output is correct |
14 |
Correct |
8 ms |
12032 KB |
Output is correct |
15 |
Correct |
8 ms |
12032 KB |
Output is correct |
16 |
Correct |
8 ms |
12032 KB |
Output is correct |
17 |
Correct |
8 ms |
12032 KB |
Output is correct |
18 |
Correct |
8 ms |
12032 KB |
Output is correct |
19 |
Correct |
8 ms |
12032 KB |
Output is correct |
20 |
Correct |
8 ms |
12032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12032 KB |
Output is correct |
2 |
Correct |
8 ms |
12032 KB |
Output is correct |
3 |
Correct |
8 ms |
12160 KB |
Output is correct |
4 |
Correct |
8 ms |
12032 KB |
Output is correct |
5 |
Correct |
8 ms |
12032 KB |
Output is correct |
6 |
Correct |
8 ms |
12032 KB |
Output is correct |
7 |
Correct |
8 ms |
12032 KB |
Output is correct |
8 |
Correct |
8 ms |
12032 KB |
Output is correct |
9 |
Correct |
8 ms |
12032 KB |
Output is correct |
10 |
Correct |
8 ms |
12032 KB |
Output is correct |
11 |
Correct |
8 ms |
12032 KB |
Output is correct |
12 |
Correct |
8 ms |
12032 KB |
Output is correct |
13 |
Correct |
9 ms |
12032 KB |
Output is correct |
14 |
Correct |
8 ms |
12032 KB |
Output is correct |
15 |
Correct |
8 ms |
12032 KB |
Output is correct |
16 |
Correct |
8 ms |
12032 KB |
Output is correct |
17 |
Correct |
8 ms |
12032 KB |
Output is correct |
18 |
Correct |
8 ms |
12032 KB |
Output is correct |
19 |
Correct |
8 ms |
12032 KB |
Output is correct |
20 |
Correct |
8 ms |
12032 KB |
Output is correct |
21 |
Correct |
8 ms |
12032 KB |
Output is correct |
22 |
Correct |
11 ms |
12160 KB |
Output is correct |
23 |
Correct |
11 ms |
12160 KB |
Output is correct |
24 |
Correct |
11 ms |
12160 KB |
Output is correct |
25 |
Correct |
10 ms |
12160 KB |
Output is correct |
26 |
Correct |
10 ms |
12160 KB |
Output is correct |
27 |
Correct |
11 ms |
12288 KB |
Output is correct |
28 |
Correct |
12 ms |
12160 KB |
Output is correct |
29 |
Correct |
10 ms |
12160 KB |
Output is correct |
30 |
Correct |
8 ms |
12032 KB |
Output is correct |
31 |
Correct |
11 ms |
12160 KB |
Output is correct |
32 |
Correct |
9 ms |
12032 KB |
Output is correct |
33 |
Correct |
8 ms |
12032 KB |
Output is correct |
34 |
Correct |
8 ms |
12032 KB |
Output is correct |
35 |
Correct |
9 ms |
12160 KB |
Output is correct |
36 |
Correct |
9 ms |
12032 KB |
Output is correct |
37 |
Correct |
9 ms |
12288 KB |
Output is correct |
38 |
Correct |
9 ms |
12160 KB |
Output is correct |
39 |
Correct |
8 ms |
12032 KB |
Output is correct |
40 |
Correct |
9 ms |
12032 KB |
Output is correct |
41 |
Correct |
9 ms |
12032 KB |
Output is correct |
42 |
Correct |
9 ms |
12032 KB |
Output is correct |
43 |
Correct |
10 ms |
12160 KB |
Output is correct |
44 |
Correct |
8 ms |
12032 KB |
Output is correct |
45 |
Correct |
9 ms |
12032 KB |
Output is correct |
46 |
Correct |
9 ms |
12160 KB |
Output is correct |
47 |
Correct |
8 ms |
12032 KB |
Output is correct |
48 |
Correct |
9 ms |
12032 KB |
Output is correct |
49 |
Correct |
10 ms |
12160 KB |
Output is correct |
50 |
Correct |
8 ms |
12032 KB |
Output is correct |
51 |
Correct |
8 ms |
12032 KB |
Output is correct |
52 |
Correct |
8 ms |
12032 KB |
Output is correct |
53 |
Correct |
9 ms |
12160 KB |
Output is correct |
54 |
Correct |
8 ms |
12032 KB |
Output is correct |
55 |
Correct |
9 ms |
12032 KB |
Output is correct |
56 |
Correct |
9 ms |
12032 KB |
Output is correct |
57 |
Correct |
9 ms |
12160 KB |
Output is correct |
58 |
Correct |
11 ms |
12160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12032 KB |
Output is correct |
2 |
Correct |
8 ms |
12032 KB |
Output is correct |
3 |
Correct |
8 ms |
12160 KB |
Output is correct |
4 |
Correct |
8 ms |
12032 KB |
Output is correct |
5 |
Correct |
8 ms |
12032 KB |
Output is correct |
6 |
Correct |
8 ms |
12032 KB |
Output is correct |
7 |
Correct |
8 ms |
12032 KB |
Output is correct |
8 |
Correct |
8 ms |
12032 KB |
Output is correct |
9 |
Correct |
8 ms |
12032 KB |
Output is correct |
10 |
Correct |
8 ms |
12032 KB |
Output is correct |
11 |
Correct |
8 ms |
12032 KB |
Output is correct |
12 |
Correct |
8 ms |
12032 KB |
Output is correct |
13 |
Correct |
9 ms |
12032 KB |
Output is correct |
14 |
Correct |
8 ms |
12032 KB |
Output is correct |
15 |
Correct |
8 ms |
12032 KB |
Output is correct |
16 |
Correct |
8 ms |
12032 KB |
Output is correct |
17 |
Correct |
8 ms |
12032 KB |
Output is correct |
18 |
Correct |
8 ms |
12032 KB |
Output is correct |
19 |
Correct |
8 ms |
12032 KB |
Output is correct |
20 |
Correct |
8 ms |
12032 KB |
Output is correct |
21 |
Correct |
8 ms |
12032 KB |
Output is correct |
22 |
Correct |
11 ms |
12160 KB |
Output is correct |
23 |
Correct |
11 ms |
12160 KB |
Output is correct |
24 |
Correct |
11 ms |
12160 KB |
Output is correct |
25 |
Correct |
10 ms |
12160 KB |
Output is correct |
26 |
Correct |
10 ms |
12160 KB |
Output is correct |
27 |
Correct |
11 ms |
12288 KB |
Output is correct |
28 |
Correct |
12 ms |
12160 KB |
Output is correct |
29 |
Correct |
10 ms |
12160 KB |
Output is correct |
30 |
Correct |
8 ms |
12032 KB |
Output is correct |
31 |
Correct |
11 ms |
12160 KB |
Output is correct |
32 |
Correct |
9 ms |
12032 KB |
Output is correct |
33 |
Correct |
8 ms |
12032 KB |
Output is correct |
34 |
Correct |
8 ms |
12032 KB |
Output is correct |
35 |
Correct |
9 ms |
12160 KB |
Output is correct |
36 |
Correct |
9 ms |
12032 KB |
Output is correct |
37 |
Correct |
9 ms |
12288 KB |
Output is correct |
38 |
Correct |
9 ms |
12160 KB |
Output is correct |
39 |
Correct |
8 ms |
12032 KB |
Output is correct |
40 |
Correct |
9 ms |
12032 KB |
Output is correct |
41 |
Correct |
9 ms |
12032 KB |
Output is correct |
42 |
Correct |
9 ms |
12032 KB |
Output is correct |
43 |
Correct |
10 ms |
12160 KB |
Output is correct |
44 |
Correct |
8 ms |
12032 KB |
Output is correct |
45 |
Correct |
9 ms |
12032 KB |
Output is correct |
46 |
Correct |
9 ms |
12160 KB |
Output is correct |
47 |
Correct |
8 ms |
12032 KB |
Output is correct |
48 |
Correct |
9 ms |
12032 KB |
Output is correct |
49 |
Correct |
10 ms |
12160 KB |
Output is correct |
50 |
Correct |
8 ms |
12032 KB |
Output is correct |
51 |
Correct |
8 ms |
12032 KB |
Output is correct |
52 |
Correct |
8 ms |
12032 KB |
Output is correct |
53 |
Correct |
9 ms |
12160 KB |
Output is correct |
54 |
Correct |
8 ms |
12032 KB |
Output is correct |
55 |
Correct |
9 ms |
12032 KB |
Output is correct |
56 |
Correct |
9 ms |
12032 KB |
Output is correct |
57 |
Correct |
9 ms |
12160 KB |
Output is correct |
58 |
Correct |
11 ms |
12160 KB |
Output is correct |
59 |
Correct |
714 ms |
36328 KB |
Output is correct |
60 |
Correct |
812 ms |
39148 KB |
Output is correct |
61 |
Correct |
8 ms |
12032 KB |
Output is correct |
62 |
Correct |
8 ms |
12032 KB |
Output is correct |
63 |
Correct |
683 ms |
33652 KB |
Output is correct |
64 |
Correct |
10 ms |
12544 KB |
Output is correct |
65 |
Correct |
21 ms |
13952 KB |
Output is correct |
66 |
Correct |
167 ms |
27892 KB |
Output is correct |
67 |
Correct |
522 ms |
46968 KB |
Output is correct |
68 |
Correct |
559 ms |
47728 KB |
Output is correct |
69 |
Correct |
34 ms |
12928 KB |
Output is correct |
70 |
Correct |
255 ms |
21348 KB |
Output is correct |
71 |
Correct |
853 ms |
42248 KB |
Output is correct |
72 |
Correct |
826 ms |
40932 KB |
Output is correct |
73 |
Correct |
177 ms |
19188 KB |
Output is correct |
74 |
Correct |
752 ms |
37868 KB |
Output is correct |
75 |
Correct |
86 ms |
15480 KB |
Output is correct |
76 |
Correct |
843 ms |
41720 KB |
Output is correct |
77 |
Correct |
843 ms |
41688 KB |
Output is correct |
78 |
Correct |
50 ms |
15736 KB |
Output is correct |
79 |
Correct |
508 ms |
45176 KB |
Output is correct |
80 |
Correct |
13 ms |
12288 KB |
Output is correct |
81 |
Correct |
252 ms |
21400 KB |
Output is correct |
82 |
Correct |
800 ms |
39652 KB |
Output is correct |
83 |
Correct |
742 ms |
37876 KB |
Output is correct |
84 |
Correct |
740 ms |
37736 KB |
Output is correct |
85 |
Correct |
738 ms |
37800 KB |
Output is correct |
86 |
Correct |
820 ms |
38888 KB |
Output is correct |
87 |
Correct |
806 ms |
38888 KB |
Output is correct |