# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
122204 |
2019-06-27T20:23:51 Z |
Gustav |
Network (BOI15_net) |
C++14 |
|
605 ms |
45340 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 998244353;
#pragma GCC optimize("Ofast")
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
int n;
vvi conn;
vpi ans;
pi dfs(int node, int par){
if(conn[node].size() == 1) return {node, -1};
pi m = {-1, -1};
for(auto x : conn[node]){
if(x == par) continue;
pi r = dfs(x, node);
if(m.first == -1) m = r;
else{
if(m.second != -1 || r.second != -1){
ans.push_back({m.first, r.first});
if(m.second == -1) m = {r.second, m.second};
else m = {m.second, r.second};
}
else{
m.second = r.first;
}
}
}
return m;
}
int main(){
cin.sync_with_stdio(false);
cin.tie(0);
cin >> n;
conn = vvi(n);
for(int i = 0; i < n-1; i++){
int u, v;
cin >> u >> v;
u--, v--;
conn[u].push_back(v);
conn[v].push_back(u);
}
int root = 0;
while(conn[root].size() == 1) root++;
pi r = dfs(root, -1);
if(r.second != -1){
ans.push_back({r.first, r.second});
}
else{
ans.push_back({root, r.first});
}
cout << ans.size() << "\n";
for(int i = 0; i < ans.size(); i++) cout << ans[i].first+1 << " " << ans[i].second+1 << "\n";
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ans.size(); i++) cout << ans[i].first+1 << " " << ans[i].second+1 << "\n";
~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
3 ms |
512 KB |
Output is correct |
23 |
Correct |
3 ms |
512 KB |
Output is correct |
24 |
Correct |
3 ms |
512 KB |
Output is correct |
25 |
Correct |
3 ms |
512 KB |
Output is correct |
26 |
Correct |
2 ms |
512 KB |
Output is correct |
27 |
Correct |
3 ms |
640 KB |
Output is correct |
28 |
Correct |
3 ms |
512 KB |
Output is correct |
29 |
Correct |
2 ms |
432 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
3 ms |
512 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
384 KB |
Output is correct |
35 |
Correct |
2 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
3 ms |
384 KB |
Output is correct |
38 |
Correct |
2 ms |
512 KB |
Output is correct |
39 |
Correct |
2 ms |
384 KB |
Output is correct |
40 |
Correct |
2 ms |
384 KB |
Output is correct |
41 |
Correct |
2 ms |
384 KB |
Output is correct |
42 |
Correct |
2 ms |
512 KB |
Output is correct |
43 |
Correct |
2 ms |
384 KB |
Output is correct |
44 |
Correct |
2 ms |
384 KB |
Output is correct |
45 |
Correct |
2 ms |
384 KB |
Output is correct |
46 |
Correct |
2 ms |
384 KB |
Output is correct |
47 |
Correct |
2 ms |
380 KB |
Output is correct |
48 |
Correct |
2 ms |
384 KB |
Output is correct |
49 |
Correct |
3 ms |
384 KB |
Output is correct |
50 |
Correct |
2 ms |
384 KB |
Output is correct |
51 |
Correct |
2 ms |
384 KB |
Output is correct |
52 |
Correct |
2 ms |
384 KB |
Output is correct |
53 |
Correct |
3 ms |
384 KB |
Output is correct |
54 |
Correct |
2 ms |
384 KB |
Output is correct |
55 |
Correct |
2 ms |
384 KB |
Output is correct |
56 |
Correct |
2 ms |
384 KB |
Output is correct |
57 |
Correct |
2 ms |
384 KB |
Output is correct |
58 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
3 ms |
512 KB |
Output is correct |
23 |
Correct |
3 ms |
512 KB |
Output is correct |
24 |
Correct |
3 ms |
512 KB |
Output is correct |
25 |
Correct |
3 ms |
512 KB |
Output is correct |
26 |
Correct |
2 ms |
512 KB |
Output is correct |
27 |
Correct |
3 ms |
640 KB |
Output is correct |
28 |
Correct |
3 ms |
512 KB |
Output is correct |
29 |
Correct |
2 ms |
432 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
3 ms |
512 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
384 KB |
Output is correct |
35 |
Correct |
2 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
3 ms |
384 KB |
Output is correct |
38 |
Correct |
2 ms |
512 KB |
Output is correct |
39 |
Correct |
2 ms |
384 KB |
Output is correct |
40 |
Correct |
2 ms |
384 KB |
Output is correct |
41 |
Correct |
2 ms |
384 KB |
Output is correct |
42 |
Correct |
2 ms |
512 KB |
Output is correct |
43 |
Correct |
2 ms |
384 KB |
Output is correct |
44 |
Correct |
2 ms |
384 KB |
Output is correct |
45 |
Correct |
2 ms |
384 KB |
Output is correct |
46 |
Correct |
2 ms |
384 KB |
Output is correct |
47 |
Correct |
2 ms |
380 KB |
Output is correct |
48 |
Correct |
2 ms |
384 KB |
Output is correct |
49 |
Correct |
3 ms |
384 KB |
Output is correct |
50 |
Correct |
2 ms |
384 KB |
Output is correct |
51 |
Correct |
2 ms |
384 KB |
Output is correct |
52 |
Correct |
2 ms |
384 KB |
Output is correct |
53 |
Correct |
3 ms |
384 KB |
Output is correct |
54 |
Correct |
2 ms |
384 KB |
Output is correct |
55 |
Correct |
2 ms |
384 KB |
Output is correct |
56 |
Correct |
2 ms |
384 KB |
Output is correct |
57 |
Correct |
2 ms |
384 KB |
Output is correct |
58 |
Correct |
3 ms |
512 KB |
Output is correct |
59 |
Correct |
439 ms |
34912 KB |
Output is correct |
60 |
Correct |
510 ms |
38744 KB |
Output is correct |
61 |
Correct |
2 ms |
384 KB |
Output is correct |
62 |
Correct |
2 ms |
384 KB |
Output is correct |
63 |
Correct |
335 ms |
31336 KB |
Output is correct |
64 |
Correct |
4 ms |
896 KB |
Output is correct |
65 |
Correct |
12 ms |
2688 KB |
Output is correct |
66 |
Correct |
190 ms |
19032 KB |
Output is correct |
67 |
Correct |
605 ms |
44664 KB |
Output is correct |
68 |
Correct |
569 ms |
45340 KB |
Output is correct |
69 |
Correct |
9 ms |
1536 KB |
Output is correct |
70 |
Correct |
100 ms |
13264 KB |
Output is correct |
71 |
Correct |
324 ms |
41828 KB |
Output is correct |
72 |
Correct |
360 ms |
40712 KB |
Output is correct |
73 |
Correct |
93 ms |
10612 KB |
Output is correct |
74 |
Correct |
498 ms |
37744 KB |
Output is correct |
75 |
Correct |
24 ms |
4836 KB |
Output is correct |
76 |
Correct |
338 ms |
41564 KB |
Output is correct |
77 |
Correct |
348 ms |
41692 KB |
Output is correct |
78 |
Correct |
29 ms |
4984 KB |
Output is correct |
79 |
Correct |
581 ms |
43400 KB |
Output is correct |
80 |
Correct |
4 ms |
640 KB |
Output is correct |
81 |
Correct |
109 ms |
13552 KB |
Output is correct |
82 |
Correct |
431 ms |
39788 KB |
Output is correct |
83 |
Correct |
513 ms |
37804 KB |
Output is correct |
84 |
Correct |
514 ms |
37740 KB |
Output is correct |
85 |
Correct |
525 ms |
37840 KB |
Output is correct |
86 |
Correct |
501 ms |
38844 KB |
Output is correct |
87 |
Correct |
507 ms |
38848 KB |
Output is correct |