# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
848225 |
2023-09-11T17:18:34 Z |
Hakiers |
Network (BOI15_net) |
C++17 |
|
608 ms |
262144 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 7;
vector<int> G[MAXN];
int parent[MAXN];
pair<int, int> dp[MAXN];
tuple<int, int, int> vein;
vector<queue<int>> Q;
queue<int> sajz;
int n;
void dfsVein(int v, int p){
if((int)G[v].size() == 1) dp[v].second = v;
else dp[v].first = -1;
int max1 = v;
for(auto u : G[v]){
if(u == p) continue;
dfsVein(u, v);
if(dp[u].first > dp[max1].first)
max1 = u;
}
// albo merguje ui z uj lub ide w gore
for(auto u : G[v])
if(u != p && u != max1) vein = max(vein, make_tuple(dp[u].first + dp[max1].first + (int)G[v].size() - 2, dp[max1].second, dp[u].second));
dp[v] = dp[max1];
dp[v].first += max((int)G[v].size() - 2, 0);
}
void dfs(int v, int p){
parent[v] = p;
for(auto u : G[v])
if(u != p) dfs(u, v);
}
void dfs_push(int v, int p){
for(auto u : G[v])
if(u != p) dfs_push(u, v);
if((int)G[v].size() == 1) sajz.push(v);
}
void compute(int u, int v){
while(u != v){
for(auto w : G[parent[u]]){
if(w == u || w == parent[parent[u]]) continue;
sajz = std::queue<int>();
dfs_push(w, parent[u]);
Q.push_back(sajz);
}
u = parent[u];
}
}
bool cmp(queue<int> &a, queue<int> &b){
return (int)a.size() > (int)b.size();
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i < n; i++){
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
dfsVein(1, 1);
auto [val, u1, u2] = vein;
dfs(u1, u1);
compute(u2, u1);
sort(Q.begin(), Q.end(), cmp);
/*
cout << " val: " << val << " u1: " << u1 << " u2:" << u2 << endl;
for(auto x : Q){
while(x.size()){
cout << (int)x.front() << " ";
x.pop();
}
cout << endl;
}
*/
vector<pair<int, int>> anserw;
anserw.push_back({u1, u2});
sajz = std::queue<int>(); // clearunemy sajza
for(auto x : Q){
while(x.size() && sajz.size()){
anserw.push_back({x.front(), sajz.front()});
x.pop();
sajz.pop();
}
while(x.size()){
sajz.push(x.front());
x.pop();
}
}
while(sajz.size()){
anserw.push_back({u1, sajz.front()});
sajz.pop();
}
cout << anserw.size() << "\n";
for(auto [x, y] : anserw)
cout << x << " " << y << "\n";
}
/*
27
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
8 10
8 11
8 12
5 13
13 14
14 15
14 16
14 17
14 18
8 19
4 20
20 21
21 22
21 23
21 24
21 25
21 26
2 27
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
15708 KB |
Output is correct |
2 |
Correct |
3 ms |
15860 KB |
Output is correct |
3 |
Correct |
4 ms |
15708 KB |
Output is correct |
4 |
Correct |
3 ms |
15704 KB |
Output is correct |
5 |
Correct |
3 ms |
15708 KB |
Output is correct |
6 |
Correct |
4 ms |
15708 KB |
Output is correct |
7 |
Correct |
3 ms |
15708 KB |
Output is correct |
8 |
Correct |
3 ms |
15708 KB |
Output is correct |
9 |
Correct |
3 ms |
15708 KB |
Output is correct |
10 |
Correct |
3 ms |
15708 KB |
Output is correct |
11 |
Correct |
3 ms |
15704 KB |
Output is correct |
12 |
Correct |
3 ms |
15708 KB |
Output is correct |
13 |
Correct |
3 ms |
15708 KB |
Output is correct |
14 |
Correct |
3 ms |
15708 KB |
Output is correct |
15 |
Correct |
3 ms |
15708 KB |
Output is correct |
16 |
Correct |
3 ms |
15704 KB |
Output is correct |
17 |
Correct |
3 ms |
15708 KB |
Output is correct |
18 |
Correct |
3 ms |
15708 KB |
Output is correct |
19 |
Correct |
3 ms |
15708 KB |
Output is correct |
20 |
Correct |
4 ms |
15704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
15708 KB |
Output is correct |
2 |
Correct |
3 ms |
15860 KB |
Output is correct |
3 |
Correct |
4 ms |
15708 KB |
Output is correct |
4 |
Correct |
3 ms |
15704 KB |
Output is correct |
5 |
Correct |
3 ms |
15708 KB |
Output is correct |
6 |
Correct |
4 ms |
15708 KB |
Output is correct |
7 |
Correct |
3 ms |
15708 KB |
Output is correct |
8 |
Correct |
3 ms |
15708 KB |
Output is correct |
9 |
Correct |
3 ms |
15708 KB |
Output is correct |
10 |
Correct |
3 ms |
15708 KB |
Output is correct |
11 |
Correct |
3 ms |
15704 KB |
Output is correct |
12 |
Correct |
3 ms |
15708 KB |
Output is correct |
13 |
Correct |
3 ms |
15708 KB |
Output is correct |
14 |
Correct |
3 ms |
15708 KB |
Output is correct |
15 |
Correct |
3 ms |
15708 KB |
Output is correct |
16 |
Correct |
3 ms |
15704 KB |
Output is correct |
17 |
Correct |
3 ms |
15708 KB |
Output is correct |
18 |
Correct |
3 ms |
15708 KB |
Output is correct |
19 |
Correct |
3 ms |
15708 KB |
Output is correct |
20 |
Correct |
4 ms |
15704 KB |
Output is correct |
21 |
Correct |
3 ms |
15704 KB |
Output is correct |
22 |
Correct |
5 ms |
17240 KB |
Output is correct |
23 |
Correct |
5 ms |
17244 KB |
Output is correct |
24 |
Correct |
5 ms |
17244 KB |
Output is correct |
25 |
Correct |
4 ms |
16476 KB |
Output is correct |
26 |
Correct |
4 ms |
16476 KB |
Output is correct |
27 |
Correct |
5 ms |
15964 KB |
Output is correct |
28 |
Correct |
4 ms |
15964 KB |
Output is correct |
29 |
Correct |
4 ms |
15964 KB |
Output is correct |
30 |
Correct |
3 ms |
15708 KB |
Output is correct |
31 |
Correct |
4 ms |
15964 KB |
Output is correct |
32 |
Correct |
3 ms |
15708 KB |
Output is correct |
33 |
Correct |
3 ms |
15704 KB |
Output is correct |
34 |
Correct |
3 ms |
15708 KB |
Output is correct |
35 |
Correct |
3 ms |
15708 KB |
Output is correct |
36 |
Correct |
3 ms |
15704 KB |
Output is correct |
37 |
Correct |
3 ms |
15708 KB |
Output is correct |
38 |
Correct |
3 ms |
15960 KB |
Output is correct |
39 |
Correct |
4 ms |
15960 KB |
Output is correct |
40 |
Correct |
5 ms |
15704 KB |
Output is correct |
41 |
Correct |
3 ms |
15704 KB |
Output is correct |
42 |
Correct |
4 ms |
16220 KB |
Output is correct |
43 |
Correct |
5 ms |
16476 KB |
Output is correct |
44 |
Correct |
3 ms |
15704 KB |
Output is correct |
45 |
Correct |
3 ms |
15708 KB |
Output is correct |
46 |
Correct |
3 ms |
15964 KB |
Output is correct |
47 |
Correct |
3 ms |
15708 KB |
Output is correct |
48 |
Correct |
3 ms |
15964 KB |
Output is correct |
49 |
Correct |
4 ms |
16476 KB |
Output is correct |
50 |
Correct |
3 ms |
15876 KB |
Output is correct |
51 |
Correct |
3 ms |
15708 KB |
Output is correct |
52 |
Correct |
3 ms |
15960 KB |
Output is correct |
53 |
Correct |
4 ms |
16112 KB |
Output is correct |
54 |
Correct |
3 ms |
15708 KB |
Output is correct |
55 |
Correct |
3 ms |
15964 KB |
Output is correct |
56 |
Correct |
4 ms |
15708 KB |
Output is correct |
57 |
Correct |
4 ms |
16220 KB |
Output is correct |
58 |
Correct |
5 ms |
17140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
15708 KB |
Output is correct |
2 |
Correct |
3 ms |
15860 KB |
Output is correct |
3 |
Correct |
4 ms |
15708 KB |
Output is correct |
4 |
Correct |
3 ms |
15704 KB |
Output is correct |
5 |
Correct |
3 ms |
15708 KB |
Output is correct |
6 |
Correct |
4 ms |
15708 KB |
Output is correct |
7 |
Correct |
3 ms |
15708 KB |
Output is correct |
8 |
Correct |
3 ms |
15708 KB |
Output is correct |
9 |
Correct |
3 ms |
15708 KB |
Output is correct |
10 |
Correct |
3 ms |
15708 KB |
Output is correct |
11 |
Correct |
3 ms |
15704 KB |
Output is correct |
12 |
Correct |
3 ms |
15708 KB |
Output is correct |
13 |
Correct |
3 ms |
15708 KB |
Output is correct |
14 |
Correct |
3 ms |
15708 KB |
Output is correct |
15 |
Correct |
3 ms |
15708 KB |
Output is correct |
16 |
Correct |
3 ms |
15704 KB |
Output is correct |
17 |
Correct |
3 ms |
15708 KB |
Output is correct |
18 |
Correct |
3 ms |
15708 KB |
Output is correct |
19 |
Correct |
3 ms |
15708 KB |
Output is correct |
20 |
Correct |
4 ms |
15704 KB |
Output is correct |
21 |
Correct |
3 ms |
15704 KB |
Output is correct |
22 |
Correct |
5 ms |
17240 KB |
Output is correct |
23 |
Correct |
5 ms |
17244 KB |
Output is correct |
24 |
Correct |
5 ms |
17244 KB |
Output is correct |
25 |
Correct |
4 ms |
16476 KB |
Output is correct |
26 |
Correct |
4 ms |
16476 KB |
Output is correct |
27 |
Correct |
5 ms |
15964 KB |
Output is correct |
28 |
Correct |
4 ms |
15964 KB |
Output is correct |
29 |
Correct |
4 ms |
15964 KB |
Output is correct |
30 |
Correct |
3 ms |
15708 KB |
Output is correct |
31 |
Correct |
4 ms |
15964 KB |
Output is correct |
32 |
Correct |
3 ms |
15708 KB |
Output is correct |
33 |
Correct |
3 ms |
15704 KB |
Output is correct |
34 |
Correct |
3 ms |
15708 KB |
Output is correct |
35 |
Correct |
3 ms |
15708 KB |
Output is correct |
36 |
Correct |
3 ms |
15704 KB |
Output is correct |
37 |
Correct |
3 ms |
15708 KB |
Output is correct |
38 |
Correct |
3 ms |
15960 KB |
Output is correct |
39 |
Correct |
4 ms |
15960 KB |
Output is correct |
40 |
Correct |
5 ms |
15704 KB |
Output is correct |
41 |
Correct |
3 ms |
15704 KB |
Output is correct |
42 |
Correct |
4 ms |
16220 KB |
Output is correct |
43 |
Correct |
5 ms |
16476 KB |
Output is correct |
44 |
Correct |
3 ms |
15704 KB |
Output is correct |
45 |
Correct |
3 ms |
15708 KB |
Output is correct |
46 |
Correct |
3 ms |
15964 KB |
Output is correct |
47 |
Correct |
3 ms |
15708 KB |
Output is correct |
48 |
Correct |
3 ms |
15964 KB |
Output is correct |
49 |
Correct |
4 ms |
16476 KB |
Output is correct |
50 |
Correct |
3 ms |
15876 KB |
Output is correct |
51 |
Correct |
3 ms |
15708 KB |
Output is correct |
52 |
Correct |
3 ms |
15960 KB |
Output is correct |
53 |
Correct |
4 ms |
16112 KB |
Output is correct |
54 |
Correct |
3 ms |
15708 KB |
Output is correct |
55 |
Correct |
3 ms |
15964 KB |
Output is correct |
56 |
Correct |
4 ms |
15708 KB |
Output is correct |
57 |
Correct |
4 ms |
16220 KB |
Output is correct |
58 |
Correct |
5 ms |
17140 KB |
Output is correct |
59 |
Correct |
530 ms |
210740 KB |
Output is correct |
60 |
Correct |
402 ms |
40828 KB |
Output is correct |
61 |
Correct |
3 ms |
15704 KB |
Output is correct |
62 |
Correct |
3 ms |
15708 KB |
Output is correct |
63 |
Correct |
402 ms |
122520 KB |
Output is correct |
64 |
Correct |
5 ms |
16472 KB |
Output is correct |
65 |
Correct |
13 ms |
21700 KB |
Output is correct |
66 |
Correct |
99 ms |
44948 KB |
Output is correct |
67 |
Correct |
480 ms |
67044 KB |
Output is correct |
68 |
Correct |
608 ms |
112088 KB |
Output is correct |
69 |
Correct |
23 ms |
27504 KB |
Output is correct |
70 |
Correct |
266 ms |
200280 KB |
Output is correct |
71 |
Runtime error |
364 ms |
262144 KB |
Execution killed with signal 9 |
72 |
Halted |
0 ms |
0 KB |
- |