# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
710821 |
2023-03-15T21:05:48 Z |
noedit |
Network (BOI15_net) |
C++17 |
|
643 ms |
65612 KB |
#include <bits/stdc++.h>
#include <quadmath.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
using namespace std;
//using namespace __gnu_pbds;
//
//#define int long long
////#define ld long double
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
vector<vector<int> > g;
vector<int> pr;
vector<int> tin, tout;
vector<int> ls;
vector<int> ord;
vector<int> tin_ord;
int timer = 0;
void dfs(int v, int p)
{
tin[v] = timer++;
pr[v] = p;
if (g[v].size() == 1){
ls[v]++;
tin_ord.push_back(tin[v]);
ord.push_back(v);
}
for (auto&u : g[v])
{
if (u != p)
{
dfs(u, v);
ls[v] += ls[u];
}
}
tout[v] = timer++;
}
int root = 0;
int cock(int v, int p)
{
for (auto& u : g[v])
{
if (u != p)
{
if (ls[u] > ls[root] / 2)
{
return cock(u, v);
}
}
}
return v;
}
void solve()
{
int n;
cin >> n;
g.resize(n);
pr.resize(n);
ls.resize(n);
tin.resize(n);
tout.resize(n);
for (int i = 0; i < n - 1; i++)
{
int x, y;
cin >> x >> y;
x--; y--;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 0; i < n; i++)
if (g[i].size() > 1)
root = i;
dfs(root, root);
vector<int> ans(ls[root] + ls[root] % 2);
vector<int> cur;
int j = cock(root, root);
int lt = lower_bound(tin_ord.begin(), tin_ord.end(), tin[j]) - tin_ord.begin();
int rt = upper_bound(tin_ord.begin(), tin_ord.end(), tout[j]) - tin_ord.begin() - 1;
int k = 0;
int fist = -1;
for (int i = 0; i < lt; i++)
{
ans[k] = ord[i];
if (fist == -1) fist = ord[i];
k += 2;
if (k == ans.size()) k = 1;
}
for (int i = rt + 1; i < ord.size(); i++)
{
ans[k] = ord[i];
if (fist == -1) fist = ord[i];
k += 2;
if (k == ans.size()) k = 1;
}
for (auto& u : g[j])
{
if (u != pr[j])
{
int l = lower_bound(tin_ord.begin(), tin_ord.end(), tin[u]) - tin_ord.begin();
int r = upper_bound(tin_ord.begin(), tin_ord.end(), tout[u]) - tin_ord.begin() - 1;
for (int i = l; i <= r; i++)
{
ans[k] = ord[i];
if (fist == -1) fist = ord[i];
k += 2;
if (k == ans.size()) k = 1;
}
}
}
if (ls[root] % 2 == 1)
{
ans[ans.size() - 1] = fist;
}
cout << ans.size() / 2 << endl;
for (int i = 0; i < ans.size(); i += 2)
{
cout << ans[i] + 1 << ' ' << ans[i + 1] + 1 << endl;
}
}
//
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
t = 1;
//cin >> t;
while (t--)
{
solve();
}
cerr << endl << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
return 0;
}
//
//
/*
17 13
1 3 1 2 1 3 1 2 1 1 2 1 2 1 2 1 3
3 1 2 3 3 2 1 2 1 3 2 2 1
*/
/*
6 9
3 2 1 6 7 4
3 2 6 10 8 9 7 1 4
*/
/*
9 8
2 1 4 6 7 8 9 10 11
8 9 10 11 1 4 6 7
*/
Compilation message
net.cpp: In function 'void solve()':
net.cpp:102:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if (k == ans.size()) k = 1;
| ~~^~~~~~~~~~~~~
net.cpp:104:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int i = rt + 1; i < ord.size(); i++)
| ~~^~~~~~~~~~~~
net.cpp:109:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | if (k == ans.size()) k = 1;
| ~~^~~~~~~~~~~~~
net.cpp:122:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | if (k == ans.size()) k = 1;
| ~~^~~~~~~~~~~~~
net.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i = 0; i < ans.size(); i += 2)
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
316 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
324 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
316 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
324 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
3 ms |
468 KB |
Output is correct |
23 |
Correct |
3 ms |
468 KB |
Output is correct |
24 |
Correct |
2 ms |
460 KB |
Output is correct |
25 |
Correct |
2 ms |
468 KB |
Output is correct |
26 |
Correct |
2 ms |
468 KB |
Output is correct |
27 |
Correct |
2 ms |
460 KB |
Output is correct |
28 |
Correct |
2 ms |
468 KB |
Output is correct |
29 |
Correct |
2 ms |
464 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
3 ms |
456 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
256 KB |
Output is correct |
35 |
Correct |
1 ms |
320 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
320 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
324 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
1 ms |
340 KB |
Output is correct |
43 |
Correct |
2 ms |
340 KB |
Output is correct |
44 |
Correct |
1 ms |
320 KB |
Output is correct |
45 |
Correct |
1 ms |
328 KB |
Output is correct |
46 |
Correct |
2 ms |
324 KB |
Output is correct |
47 |
Correct |
1 ms |
212 KB |
Output is correct |
48 |
Correct |
1 ms |
340 KB |
Output is correct |
49 |
Correct |
2 ms |
340 KB |
Output is correct |
50 |
Correct |
1 ms |
212 KB |
Output is correct |
51 |
Correct |
1 ms |
212 KB |
Output is correct |
52 |
Correct |
1 ms |
344 KB |
Output is correct |
53 |
Correct |
1 ms |
340 KB |
Output is correct |
54 |
Correct |
1 ms |
320 KB |
Output is correct |
55 |
Correct |
1 ms |
356 KB |
Output is correct |
56 |
Correct |
2 ms |
320 KB |
Output is correct |
57 |
Correct |
1 ms |
324 KB |
Output is correct |
58 |
Correct |
3 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
316 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
324 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
3 ms |
468 KB |
Output is correct |
23 |
Correct |
3 ms |
468 KB |
Output is correct |
24 |
Correct |
2 ms |
460 KB |
Output is correct |
25 |
Correct |
2 ms |
468 KB |
Output is correct |
26 |
Correct |
2 ms |
468 KB |
Output is correct |
27 |
Correct |
2 ms |
460 KB |
Output is correct |
28 |
Correct |
2 ms |
468 KB |
Output is correct |
29 |
Correct |
2 ms |
464 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
3 ms |
456 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
256 KB |
Output is correct |
35 |
Correct |
1 ms |
320 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
320 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
324 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
1 ms |
340 KB |
Output is correct |
43 |
Correct |
2 ms |
340 KB |
Output is correct |
44 |
Correct |
1 ms |
320 KB |
Output is correct |
45 |
Correct |
1 ms |
328 KB |
Output is correct |
46 |
Correct |
2 ms |
324 KB |
Output is correct |
47 |
Correct |
1 ms |
212 KB |
Output is correct |
48 |
Correct |
1 ms |
340 KB |
Output is correct |
49 |
Correct |
2 ms |
340 KB |
Output is correct |
50 |
Correct |
1 ms |
212 KB |
Output is correct |
51 |
Correct |
1 ms |
212 KB |
Output is correct |
52 |
Correct |
1 ms |
344 KB |
Output is correct |
53 |
Correct |
1 ms |
340 KB |
Output is correct |
54 |
Correct |
1 ms |
320 KB |
Output is correct |
55 |
Correct |
1 ms |
356 KB |
Output is correct |
56 |
Correct |
2 ms |
320 KB |
Output is correct |
57 |
Correct |
1 ms |
324 KB |
Output is correct |
58 |
Correct |
3 ms |
468 KB |
Output is correct |
59 |
Correct |
537 ms |
44312 KB |
Output is correct |
60 |
Correct |
582 ms |
49324 KB |
Output is correct |
61 |
Correct |
1 ms |
320 KB |
Output is correct |
62 |
Correct |
1 ms |
212 KB |
Output is correct |
63 |
Correct |
455 ms |
40616 KB |
Output is correct |
64 |
Correct |
2 ms |
852 KB |
Output is correct |
65 |
Correct |
10 ms |
2900 KB |
Output is correct |
66 |
Correct |
123 ms |
20432 KB |
Output is correct |
67 |
Correct |
426 ms |
65612 KB |
Output is correct |
68 |
Correct |
473 ms |
58852 KB |
Output is correct |
69 |
Correct |
15 ms |
1868 KB |
Output is correct |
70 |
Correct |
167 ms |
16804 KB |
Output is correct |
71 |
Correct |
607 ms |
54996 KB |
Output is correct |
72 |
Correct |
643 ms |
53580 KB |
Output is correct |
73 |
Correct |
112 ms |
13440 KB |
Output is correct |
74 |
Correct |
528 ms |
47596 KB |
Output is correct |
75 |
Correct |
52 ms |
6004 KB |
Output is correct |
76 |
Correct |
582 ms |
53084 KB |
Output is correct |
77 |
Correct |
589 ms |
53368 KB |
Output is correct |
78 |
Correct |
31 ms |
5840 KB |
Output is correct |
79 |
Correct |
430 ms |
52868 KB |
Output is correct |
80 |
Correct |
4 ms |
724 KB |
Output is correct |
81 |
Correct |
160 ms |
17348 KB |
Output is correct |
82 |
Correct |
575 ms |
50404 KB |
Output is correct |
83 |
Correct |
536 ms |
47524 KB |
Output is correct |
84 |
Correct |
543 ms |
47560 KB |
Output is correct |
85 |
Correct |
551 ms |
47576 KB |
Output is correct |
86 |
Correct |
579 ms |
49316 KB |
Output is correct |
87 |
Correct |
600 ms |
49232 KB |
Output is correct |