# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
848230 |
2023-09-11T17:39:24 Z |
Hakiers |
Network (BOI15_net) |
C++17 |
|
544 ms |
77084 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<vector<int>> Q;
vector<int> xd;
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) xd.push_back(v);
}
void compute(int u, int v){
while(u != v){
for(auto w : G[parent[u]]){
if(w == u || w == parent[parent[u]]) continue;
xd.clear();
xd.shrink_to_fit();
dfs_push(w, parent[u]);
Q.push_back(xd);
}
u = parent[u];
}
}
bool cmp(vector<int> &a, vector<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});
queue<int> sajz;
for(auto x : Q){
int it = 0;
for(; it < (int)x.size() && sajz.size(); it++){
anserw.push_back({x[it], sajz.front()});
sajz.pop();
}
for(; it < (int)x.size(); it++)
sajz.push(x[it]);
/*
while(Q[x].size() && sajz.size()){
anserw.push_back({Q[x].front(), sajz.front()});
Q[x].pop();
sajz.pop();
}
while(Q[x].size()){
sajz.push(Q[x].front());
Q[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 |
4 ms |
16008 KB |
Output is correct |
2 |
Correct |
4 ms |
15708 KB |
Output is correct |
3 |
Correct |
3 ms |
15708 KB |
Output is correct |
4 |
Correct |
3 ms |
15708 KB |
Output is correct |
5 |
Correct |
4 ms |
15704 KB |
Output is correct |
6 |
Correct |
3 ms |
15708 KB |
Output is correct |
7 |
Correct |
3 ms |
15708 KB |
Output is correct |
8 |
Correct |
4 ms |
15708 KB |
Output is correct |
9 |
Correct |
4 ms |
15816 KB |
Output is correct |
10 |
Correct |
4 ms |
15708 KB |
Output is correct |
11 |
Correct |
3 ms |
15708 KB |
Output is correct |
12 |
Correct |
3 ms |
15708 KB |
Output is correct |
13 |
Correct |
3 ms |
15852 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 |
15708 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 |
3 ms |
15708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16008 KB |
Output is correct |
2 |
Correct |
4 ms |
15708 KB |
Output is correct |
3 |
Correct |
3 ms |
15708 KB |
Output is correct |
4 |
Correct |
3 ms |
15708 KB |
Output is correct |
5 |
Correct |
4 ms |
15704 KB |
Output is correct |
6 |
Correct |
3 ms |
15708 KB |
Output is correct |
7 |
Correct |
3 ms |
15708 KB |
Output is correct |
8 |
Correct |
4 ms |
15708 KB |
Output is correct |
9 |
Correct |
4 ms |
15816 KB |
Output is correct |
10 |
Correct |
4 ms |
15708 KB |
Output is correct |
11 |
Correct |
3 ms |
15708 KB |
Output is correct |
12 |
Correct |
3 ms |
15708 KB |
Output is correct |
13 |
Correct |
3 ms |
15852 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 |
15708 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 |
3 ms |
15708 KB |
Output is correct |
21 |
Correct |
3 ms |
15964 KB |
Output is correct |
22 |
Correct |
4 ms |
15964 KB |
Output is correct |
23 |
Correct |
4 ms |
15964 KB |
Output is correct |
24 |
Correct |
4 ms |
15964 KB |
Output is correct |
25 |
Correct |
4 ms |
15964 KB |
Output is correct |
26 |
Correct |
4 ms |
15964 KB |
Output is correct |
27 |
Correct |
4 ms |
15964 KB |
Output is correct |
28 |
Correct |
4 ms |
15964 KB |
Output is correct |
29 |
Correct |
5 ms |
15708 KB |
Output is correct |
30 |
Correct |
3 ms |
15708 KB |
Output is correct |
31 |
Correct |
4 ms |
15964 KB |
Output is correct |
32 |
Correct |
4 ms |
15960 KB |
Output is correct |
33 |
Correct |
3 ms |
15708 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 |
15708 KB |
Output is correct |
37 |
Correct |
3 ms |
15708 KB |
Output is correct |
38 |
Correct |
4 ms |
15964 KB |
Output is correct |
39 |
Correct |
4 ms |
15708 KB |
Output is correct |
40 |
Correct |
3 ms |
15708 KB |
Output is correct |
41 |
Correct |
3 ms |
15708 KB |
Output is correct |
42 |
Correct |
4 ms |
15708 KB |
Output is correct |
43 |
Correct |
3 ms |
15964 KB |
Output is correct |
44 |
Correct |
3 ms |
15708 KB |
Output is correct |
45 |
Correct |
3 ms |
15708 KB |
Output is correct |
46 |
Correct |
3 ms |
15704 KB |
Output is correct |
47 |
Correct |
3 ms |
15708 KB |
Output is correct |
48 |
Correct |
3 ms |
15708 KB |
Output is correct |
49 |
Correct |
4 ms |
15964 KB |
Output is correct |
50 |
Correct |
3 ms |
15708 KB |
Output is correct |
51 |
Correct |
3 ms |
15708 KB |
Output is correct |
52 |
Correct |
3 ms |
15708 KB |
Output is correct |
53 |
Correct |
3 ms |
15708 KB |
Output is correct |
54 |
Correct |
3 ms |
15704 KB |
Output is correct |
55 |
Correct |
3 ms |
15704 KB |
Output is correct |
56 |
Correct |
3 ms |
15708 KB |
Output is correct |
57 |
Correct |
3 ms |
15708 KB |
Output is correct |
58 |
Correct |
4 ms |
15964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16008 KB |
Output is correct |
2 |
Correct |
4 ms |
15708 KB |
Output is correct |
3 |
Correct |
3 ms |
15708 KB |
Output is correct |
4 |
Correct |
3 ms |
15708 KB |
Output is correct |
5 |
Correct |
4 ms |
15704 KB |
Output is correct |
6 |
Correct |
3 ms |
15708 KB |
Output is correct |
7 |
Correct |
3 ms |
15708 KB |
Output is correct |
8 |
Correct |
4 ms |
15708 KB |
Output is correct |
9 |
Correct |
4 ms |
15816 KB |
Output is correct |
10 |
Correct |
4 ms |
15708 KB |
Output is correct |
11 |
Correct |
3 ms |
15708 KB |
Output is correct |
12 |
Correct |
3 ms |
15708 KB |
Output is correct |
13 |
Correct |
3 ms |
15852 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 |
15708 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 |
3 ms |
15708 KB |
Output is correct |
21 |
Correct |
3 ms |
15964 KB |
Output is correct |
22 |
Correct |
4 ms |
15964 KB |
Output is correct |
23 |
Correct |
4 ms |
15964 KB |
Output is correct |
24 |
Correct |
4 ms |
15964 KB |
Output is correct |
25 |
Correct |
4 ms |
15964 KB |
Output is correct |
26 |
Correct |
4 ms |
15964 KB |
Output is correct |
27 |
Correct |
4 ms |
15964 KB |
Output is correct |
28 |
Correct |
4 ms |
15964 KB |
Output is correct |
29 |
Correct |
5 ms |
15708 KB |
Output is correct |
30 |
Correct |
3 ms |
15708 KB |
Output is correct |
31 |
Correct |
4 ms |
15964 KB |
Output is correct |
32 |
Correct |
4 ms |
15960 KB |
Output is correct |
33 |
Correct |
3 ms |
15708 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 |
15708 KB |
Output is correct |
37 |
Correct |
3 ms |
15708 KB |
Output is correct |
38 |
Correct |
4 ms |
15964 KB |
Output is correct |
39 |
Correct |
4 ms |
15708 KB |
Output is correct |
40 |
Correct |
3 ms |
15708 KB |
Output is correct |
41 |
Correct |
3 ms |
15708 KB |
Output is correct |
42 |
Correct |
4 ms |
15708 KB |
Output is correct |
43 |
Correct |
3 ms |
15964 KB |
Output is correct |
44 |
Correct |
3 ms |
15708 KB |
Output is correct |
45 |
Correct |
3 ms |
15708 KB |
Output is correct |
46 |
Correct |
3 ms |
15704 KB |
Output is correct |
47 |
Correct |
3 ms |
15708 KB |
Output is correct |
48 |
Correct |
3 ms |
15708 KB |
Output is correct |
49 |
Correct |
4 ms |
15964 KB |
Output is correct |
50 |
Correct |
3 ms |
15708 KB |
Output is correct |
51 |
Correct |
3 ms |
15708 KB |
Output is correct |
52 |
Correct |
3 ms |
15708 KB |
Output is correct |
53 |
Correct |
3 ms |
15708 KB |
Output is correct |
54 |
Correct |
3 ms |
15704 KB |
Output is correct |
55 |
Correct |
3 ms |
15704 KB |
Output is correct |
56 |
Correct |
3 ms |
15708 KB |
Output is correct |
57 |
Correct |
3 ms |
15708 KB |
Output is correct |
58 |
Correct |
4 ms |
15964 KB |
Output is correct |
59 |
Correct |
381 ms |
47584 KB |
Output is correct |
60 |
Correct |
365 ms |
39768 KB |
Output is correct |
61 |
Correct |
3 ms |
15708 KB |
Output is correct |
62 |
Correct |
3 ms |
15708 KB |
Output is correct |
63 |
Correct |
299 ms |
41880 KB |
Output is correct |
64 |
Correct |
5 ms |
16476 KB |
Output is correct |
65 |
Correct |
12 ms |
21084 KB |
Output is correct |
66 |
Correct |
103 ms |
44952 KB |
Output is correct |
67 |
Correct |
486 ms |
67156 KB |
Output is correct |
68 |
Correct |
529 ms |
70652 KB |
Output is correct |
69 |
Correct |
12 ms |
17300 KB |
Output is correct |
70 |
Correct |
75 ms |
35652 KB |
Output is correct |
71 |
Correct |
327 ms |
77084 KB |
Output is correct |
72 |
Correct |
336 ms |
74736 KB |
Output is correct |
73 |
Correct |
54 ms |
25292 KB |
Output is correct |
74 |
Correct |
393 ms |
44820 KB |
Output is correct |
75 |
Correct |
27 ms |
24072 KB |
Output is correct |
76 |
Correct |
333 ms |
76572 KB |
Output is correct |
77 |
Correct |
337 ms |
76820 KB |
Output is correct |
78 |
Correct |
25 ms |
22928 KB |
Output is correct |
79 |
Correct |
544 ms |
69204 KB |
Output is correct |
80 |
Correct |
5 ms |
16220 KB |
Output is correct |
81 |
Correct |
83 ms |
33428 KB |
Output is correct |
82 |
Correct |
378 ms |
61976 KB |
Output is correct |
83 |
Correct |
421 ms |
45000 KB |
Output is correct |
84 |
Correct |
403 ms |
45056 KB |
Output is correct |
85 |
Correct |
421 ms |
45180 KB |
Output is correct |
86 |
Correct |
408 ms |
46436 KB |
Output is correct |
87 |
Correct |
370 ms |
46816 KB |
Output is correct |