# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
641295 |
2022-09-16T10:17:44 Z |
ghostwriter |
Network (BOI15_net) |
C++14 |
|
543 ms |
94520 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
Tran The Bao
CTL - Da Lat
Cay ngay cay dem nhung deo duoc cong nhan
*/
const int N = 5e5 + 5;
int n, root, cntl[N], cnt = 0;
vi adj[N], a[N], leafs;
vpi ans;
multiset<pi, greater<pi> > s;
void dfs(int u, int p) {
EACH(v, adj[u]) {
if (v == p) continue;
dfs(v, u);
cntl[u] += cntl[v];
}
if (sz(adj[u]) == 1) {
leafs.pb(u);
cntl[u] = 1;
}
}
int fct(int u, int p, int s) {
EACH(v, adj[u]) {
if (v == p || sz(adj[v]) == 1) continue;
if (cntl[v] > s / 2) return fct(v, u, s);
}
return u;
}
void dfs1(int u, int p) {
EACH(v, adj[u]) {
if (v == p) continue;
if (u == root) ++cnt;
dfs1(v, u);
}
if (sz(adj[u]) == 1) a[cnt].pb(u);
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n;
FOR(i, 1, n - 1) {
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
FOR(i, 1, n)
if (sz(adj[i]) > 1)
root = i;
dfs(root, 0);
root = fct(root, 0, cntl[root]);
dfs1(root, 0);
FOR(i, 1, cnt) s.insert({sz(a[i]), i});
WHILE(sz(s) > 1) {
int u = (*s.begin()).nd, v = (*++s.begin()).nd;
s.erase(s.begin());
s.erase(s.begin());
ans.pb({a[u].back(), a[v].back()});
a[u]._pb();
a[v]._pb();
if (!a[u].empty()) s.insert({sz(a[u]), u});
if (!a[v].empty()) s.insert({sz(a[v]), v});
}
if (!s.empty()) {
int u = a[(*s.begin()).nd].back();
ans.pb({u, u == leafs[0]? leafs[1] : leafs[0]});
}
cout << sz(ans) << '\n';
EACH(i, ans) cout << i.st << ' ' << i.nd << '\n';
return 0;
}
/*
9
2 1
3 2
4 3
5 4
6 2
7 5
8 5
9 7
*/
Compilation message
net.cpp: In function 'void dfs(int, int)':
net.cpp:26:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
26 | #define EACH(i, x) for (auto &(i) : (x))
| ^
net.cpp:42:2: note: in expansion of macro 'EACH'
42 | EACH(v, adj[u]) {
| ^~~~
net.cpp: In function 'int fct(int, int, int)':
net.cpp:26:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
26 | #define EACH(i, x) for (auto &(i) : (x))
| ^
net.cpp:53:2: note: in expansion of macro 'EACH'
53 | EACH(v, adj[u]) {
| ^~~~
net.cpp: In function 'void dfs1(int, int)':
net.cpp:26:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
26 | #define EACH(i, x) for (auto &(i) : (x))
| ^
net.cpp:60:2: note: in expansion of macro 'EACH'
60 | EACH(v, adj[u]) {
| ^~~~
net.cpp: In function 'int main()':
net.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
net.cpp:72:5: note: in expansion of macro 'FOR'
72 | FOR(i, 1, n - 1) {
| ^~~
net.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
net.cpp:78:5: note: in expansion of macro 'FOR'
78 | FOR(i, 1, n)
| ^~~
net.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
net.cpp:84:5: note: in expansion of macro 'FOR'
84 | FOR(i, 1, cnt) s.insert({sz(a[i]), i});
| ^~~
net.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define EACH(i, x) for (auto &(i) : (x))
| ^
net.cpp:100:5: note: in expansion of macro 'EACH'
100 | EACH(i, ans) cout << i.st << ' ' << i.nd << '\n';
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
11 ms |
23816 KB |
Output is correct |
3 |
Correct |
11 ms |
23812 KB |
Output is correct |
4 |
Correct |
11 ms |
23764 KB |
Output is correct |
5 |
Correct |
11 ms |
23764 KB |
Output is correct |
6 |
Correct |
14 ms |
23764 KB |
Output is correct |
7 |
Correct |
15 ms |
23764 KB |
Output is correct |
8 |
Correct |
13 ms |
23804 KB |
Output is correct |
9 |
Correct |
13 ms |
23764 KB |
Output is correct |
10 |
Correct |
13 ms |
23700 KB |
Output is correct |
11 |
Correct |
13 ms |
23764 KB |
Output is correct |
12 |
Correct |
13 ms |
23812 KB |
Output is correct |
13 |
Correct |
13 ms |
23820 KB |
Output is correct |
14 |
Correct |
12 ms |
23764 KB |
Output is correct |
15 |
Correct |
13 ms |
23820 KB |
Output is correct |
16 |
Correct |
13 ms |
23764 KB |
Output is correct |
17 |
Correct |
12 ms |
23764 KB |
Output is correct |
18 |
Correct |
13 ms |
23744 KB |
Output is correct |
19 |
Correct |
13 ms |
23764 KB |
Output is correct |
20 |
Correct |
12 ms |
23764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
11 ms |
23816 KB |
Output is correct |
3 |
Correct |
11 ms |
23812 KB |
Output is correct |
4 |
Correct |
11 ms |
23764 KB |
Output is correct |
5 |
Correct |
11 ms |
23764 KB |
Output is correct |
6 |
Correct |
14 ms |
23764 KB |
Output is correct |
7 |
Correct |
15 ms |
23764 KB |
Output is correct |
8 |
Correct |
13 ms |
23804 KB |
Output is correct |
9 |
Correct |
13 ms |
23764 KB |
Output is correct |
10 |
Correct |
13 ms |
23700 KB |
Output is correct |
11 |
Correct |
13 ms |
23764 KB |
Output is correct |
12 |
Correct |
13 ms |
23812 KB |
Output is correct |
13 |
Correct |
13 ms |
23820 KB |
Output is correct |
14 |
Correct |
12 ms |
23764 KB |
Output is correct |
15 |
Correct |
13 ms |
23820 KB |
Output is correct |
16 |
Correct |
13 ms |
23764 KB |
Output is correct |
17 |
Correct |
12 ms |
23764 KB |
Output is correct |
18 |
Correct |
13 ms |
23744 KB |
Output is correct |
19 |
Correct |
13 ms |
23764 KB |
Output is correct |
20 |
Correct |
12 ms |
23764 KB |
Output is correct |
21 |
Correct |
13 ms |
23768 KB |
Output is correct |
22 |
Correct |
14 ms |
23996 KB |
Output is correct |
23 |
Correct |
13 ms |
24020 KB |
Output is correct |
24 |
Correct |
14 ms |
23996 KB |
Output is correct |
25 |
Correct |
14 ms |
23960 KB |
Output is correct |
26 |
Correct |
15 ms |
23900 KB |
Output is correct |
27 |
Correct |
14 ms |
23892 KB |
Output is correct |
28 |
Correct |
13 ms |
23892 KB |
Output is correct |
29 |
Correct |
13 ms |
23828 KB |
Output is correct |
30 |
Correct |
12 ms |
23764 KB |
Output is correct |
31 |
Correct |
13 ms |
23892 KB |
Output is correct |
32 |
Correct |
14 ms |
23724 KB |
Output is correct |
33 |
Correct |
12 ms |
23764 KB |
Output is correct |
34 |
Correct |
12 ms |
23716 KB |
Output is correct |
35 |
Correct |
13 ms |
23816 KB |
Output is correct |
36 |
Correct |
13 ms |
23764 KB |
Output is correct |
37 |
Correct |
12 ms |
23764 KB |
Output is correct |
38 |
Correct |
14 ms |
23820 KB |
Output is correct |
39 |
Correct |
12 ms |
23764 KB |
Output is correct |
40 |
Correct |
12 ms |
23788 KB |
Output is correct |
41 |
Correct |
13 ms |
23816 KB |
Output is correct |
42 |
Correct |
12 ms |
23852 KB |
Output is correct |
43 |
Correct |
13 ms |
23912 KB |
Output is correct |
44 |
Correct |
12 ms |
23800 KB |
Output is correct |
45 |
Correct |
13 ms |
23812 KB |
Output is correct |
46 |
Correct |
14 ms |
23764 KB |
Output is correct |
47 |
Correct |
12 ms |
23764 KB |
Output is correct |
48 |
Correct |
12 ms |
23816 KB |
Output is correct |
49 |
Correct |
12 ms |
23820 KB |
Output is correct |
50 |
Correct |
12 ms |
23816 KB |
Output is correct |
51 |
Correct |
12 ms |
23764 KB |
Output is correct |
52 |
Correct |
13 ms |
23764 KB |
Output is correct |
53 |
Correct |
13 ms |
23764 KB |
Output is correct |
54 |
Correct |
13 ms |
23816 KB |
Output is correct |
55 |
Correct |
13 ms |
23836 KB |
Output is correct |
56 |
Correct |
12 ms |
23764 KB |
Output is correct |
57 |
Correct |
13 ms |
23760 KB |
Output is correct |
58 |
Correct |
13 ms |
23892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
11 ms |
23816 KB |
Output is correct |
3 |
Correct |
11 ms |
23812 KB |
Output is correct |
4 |
Correct |
11 ms |
23764 KB |
Output is correct |
5 |
Correct |
11 ms |
23764 KB |
Output is correct |
6 |
Correct |
14 ms |
23764 KB |
Output is correct |
7 |
Correct |
15 ms |
23764 KB |
Output is correct |
8 |
Correct |
13 ms |
23804 KB |
Output is correct |
9 |
Correct |
13 ms |
23764 KB |
Output is correct |
10 |
Correct |
13 ms |
23700 KB |
Output is correct |
11 |
Correct |
13 ms |
23764 KB |
Output is correct |
12 |
Correct |
13 ms |
23812 KB |
Output is correct |
13 |
Correct |
13 ms |
23820 KB |
Output is correct |
14 |
Correct |
12 ms |
23764 KB |
Output is correct |
15 |
Correct |
13 ms |
23820 KB |
Output is correct |
16 |
Correct |
13 ms |
23764 KB |
Output is correct |
17 |
Correct |
12 ms |
23764 KB |
Output is correct |
18 |
Correct |
13 ms |
23744 KB |
Output is correct |
19 |
Correct |
13 ms |
23764 KB |
Output is correct |
20 |
Correct |
12 ms |
23764 KB |
Output is correct |
21 |
Correct |
13 ms |
23768 KB |
Output is correct |
22 |
Correct |
14 ms |
23996 KB |
Output is correct |
23 |
Correct |
13 ms |
24020 KB |
Output is correct |
24 |
Correct |
14 ms |
23996 KB |
Output is correct |
25 |
Correct |
14 ms |
23960 KB |
Output is correct |
26 |
Correct |
15 ms |
23900 KB |
Output is correct |
27 |
Correct |
14 ms |
23892 KB |
Output is correct |
28 |
Correct |
13 ms |
23892 KB |
Output is correct |
29 |
Correct |
13 ms |
23828 KB |
Output is correct |
30 |
Correct |
12 ms |
23764 KB |
Output is correct |
31 |
Correct |
13 ms |
23892 KB |
Output is correct |
32 |
Correct |
14 ms |
23724 KB |
Output is correct |
33 |
Correct |
12 ms |
23764 KB |
Output is correct |
34 |
Correct |
12 ms |
23716 KB |
Output is correct |
35 |
Correct |
13 ms |
23816 KB |
Output is correct |
36 |
Correct |
13 ms |
23764 KB |
Output is correct |
37 |
Correct |
12 ms |
23764 KB |
Output is correct |
38 |
Correct |
14 ms |
23820 KB |
Output is correct |
39 |
Correct |
12 ms |
23764 KB |
Output is correct |
40 |
Correct |
12 ms |
23788 KB |
Output is correct |
41 |
Correct |
13 ms |
23816 KB |
Output is correct |
42 |
Correct |
12 ms |
23852 KB |
Output is correct |
43 |
Correct |
13 ms |
23912 KB |
Output is correct |
44 |
Correct |
12 ms |
23800 KB |
Output is correct |
45 |
Correct |
13 ms |
23812 KB |
Output is correct |
46 |
Correct |
14 ms |
23764 KB |
Output is correct |
47 |
Correct |
12 ms |
23764 KB |
Output is correct |
48 |
Correct |
12 ms |
23816 KB |
Output is correct |
49 |
Correct |
12 ms |
23820 KB |
Output is correct |
50 |
Correct |
12 ms |
23816 KB |
Output is correct |
51 |
Correct |
12 ms |
23764 KB |
Output is correct |
52 |
Correct |
13 ms |
23764 KB |
Output is correct |
53 |
Correct |
13 ms |
23764 KB |
Output is correct |
54 |
Correct |
13 ms |
23816 KB |
Output is correct |
55 |
Correct |
13 ms |
23836 KB |
Output is correct |
56 |
Correct |
12 ms |
23764 KB |
Output is correct |
57 |
Correct |
13 ms |
23760 KB |
Output is correct |
58 |
Correct |
13 ms |
23892 KB |
Output is correct |
59 |
Correct |
430 ms |
61292 KB |
Output is correct |
60 |
Correct |
422 ms |
57176 KB |
Output is correct |
61 |
Correct |
12 ms |
23744 KB |
Output is correct |
62 |
Correct |
12 ms |
23764 KB |
Output is correct |
63 |
Correct |
378 ms |
54672 KB |
Output is correct |
64 |
Correct |
15 ms |
24224 KB |
Output is correct |
65 |
Correct |
22 ms |
25804 KB |
Output is correct |
66 |
Correct |
151 ms |
39344 KB |
Output is correct |
67 |
Correct |
525 ms |
79312 KB |
Output is correct |
68 |
Correct |
543 ms |
70120 KB |
Output is correct |
69 |
Correct |
21 ms |
25804 KB |
Output is correct |
70 |
Correct |
117 ms |
44532 KB |
Output is correct |
71 |
Correct |
440 ms |
94520 KB |
Output is correct |
72 |
Correct |
435 ms |
89404 KB |
Output is correct |
73 |
Correct |
88 ms |
32316 KB |
Output is correct |
74 |
Correct |
435 ms |
54348 KB |
Output is correct |
75 |
Correct |
38 ms |
29208 KB |
Output is correct |
76 |
Correct |
352 ms |
75052 KB |
Output is correct |
77 |
Correct |
376 ms |
75700 KB |
Output is correct |
78 |
Correct |
34 ms |
27724 KB |
Output is correct |
79 |
Correct |
523 ms |
62392 KB |
Output is correct |
80 |
Correct |
14 ms |
24148 KB |
Output is correct |
81 |
Correct |
124 ms |
40576 KB |
Output is correct |
82 |
Correct |
445 ms |
73084 KB |
Output is correct |
83 |
Correct |
441 ms |
54256 KB |
Output is correct |
84 |
Correct |
438 ms |
54476 KB |
Output is correct |
85 |
Correct |
459 ms |
54724 KB |
Output is correct |
86 |
Correct |
430 ms |
57368 KB |
Output is correct |
87 |
Correct |
417 ms |
57468 KB |
Output is correct |