# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
656257 |
2022-11-06T16:11:34 Z |
ilia_rr |
Network (BOI15_net) |
C++17 |
|
31 ms |
55124 KB |
// بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
// Written by Ilia Rahbar
// #pragma GCC optimize ("O3,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target ("abm,bmi,bmi2,tbm,avx2")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define ai(x) array <int, x>
#define F first
#define S second
const int MOD = 1e9 + 7, N = 1e6 + 100;
int q, c, n, u, v, d[N], stc, l, r;
vector <int> g[N], st[N], ans[2];
int ffv(int inx)
{
memset(d, 0, sizeof d);
queue <int> q;
d[inx] = 1;
q.push(inx);
while (q.size())
{
inx = q.front();
q.pop();
for (auto i : g[inx])
{
if (!d[i])
{
d[i] = d[inx] + 1;
q.push(i);
}
}
}
return inx;
}
void dfs(int inx)
{
if (g[inx].size() == 1)
st[stc].push_back(inx);
for (auto i : g[inx])
{
if (!d[i])
{
d[i] = 1;
dfs(i);
}
}
}
int32_t main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i < n; i++)
cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
q = ffv(1);
q = ffv(q);
for (int i = 1; i <= n; i++)
{
if (d[i] == (d[q] + 1) / 2)
{
c = i;
break;
}
}
memset(d, 0, sizeof d);
d[c] = 1;
for (auto i : g[c])
{
dfs(i);
stc++;
}
sort(st, st+stc, [](vector <int> &x, vector <int> &y){return (x.size() < y.size());});
l = 0;
r = stc-1;
while (st[r].size())
{
for (int i = r-1; st[r].size() && i >= l; i--)
{
ans[0].push_back(st[r].back());
ans[1].push_back(st[i].back());
st[r].pop_back();
st[i].pop_back();
}
while (l < r && st[r].empty())
r--;
while (l < r && st[l].empty())
l++;
if (l == r)
{
while (st[r].size())
{
ans[0].push_back(st[r].back());
st[r].pop_back();
if (st[r].size())
{
ans[1].push_back(st[r].back());
st[r].pop_back();
}
else
ans[1].push_back(c);
}
}
}
cout << ans[0].size() << "\n";
for (int i = 0; i < int(ans[0].size()); i++)
cout << ans[0][i] << " " << ans[1][i] << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
54988 KB |
Output is correct |
2 |
Correct |
28 ms |
55036 KB |
Output is correct |
3 |
Correct |
28 ms |
55092 KB |
Output is correct |
4 |
Correct |
28 ms |
55100 KB |
Output is correct |
5 |
Correct |
27 ms |
55100 KB |
Output is correct |
6 |
Correct |
30 ms |
55060 KB |
Output is correct |
7 |
Correct |
29 ms |
54988 KB |
Output is correct |
8 |
Correct |
31 ms |
55008 KB |
Output is correct |
9 |
Correct |
28 ms |
55124 KB |
Output is correct |
10 |
Correct |
30 ms |
55076 KB |
Output is correct |
11 |
Correct |
28 ms |
55016 KB |
Output is correct |
12 |
Correct |
28 ms |
55048 KB |
Output is correct |
13 |
Correct |
28 ms |
55036 KB |
Output is correct |
14 |
Correct |
27 ms |
55020 KB |
Output is correct |
15 |
Correct |
29 ms |
54996 KB |
Output is correct |
16 |
Correct |
28 ms |
54996 KB |
Output is correct |
17 |
Incorrect |
31 ms |
54996 KB |
Invalid number of links. |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
54988 KB |
Output is correct |
2 |
Correct |
28 ms |
55036 KB |
Output is correct |
3 |
Correct |
28 ms |
55092 KB |
Output is correct |
4 |
Correct |
28 ms |
55100 KB |
Output is correct |
5 |
Correct |
27 ms |
55100 KB |
Output is correct |
6 |
Correct |
30 ms |
55060 KB |
Output is correct |
7 |
Correct |
29 ms |
54988 KB |
Output is correct |
8 |
Correct |
31 ms |
55008 KB |
Output is correct |
9 |
Correct |
28 ms |
55124 KB |
Output is correct |
10 |
Correct |
30 ms |
55076 KB |
Output is correct |
11 |
Correct |
28 ms |
55016 KB |
Output is correct |
12 |
Correct |
28 ms |
55048 KB |
Output is correct |
13 |
Correct |
28 ms |
55036 KB |
Output is correct |
14 |
Correct |
27 ms |
55020 KB |
Output is correct |
15 |
Correct |
29 ms |
54996 KB |
Output is correct |
16 |
Correct |
28 ms |
54996 KB |
Output is correct |
17 |
Incorrect |
31 ms |
54996 KB |
Invalid number of links. |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
54988 KB |
Output is correct |
2 |
Correct |
28 ms |
55036 KB |
Output is correct |
3 |
Correct |
28 ms |
55092 KB |
Output is correct |
4 |
Correct |
28 ms |
55100 KB |
Output is correct |
5 |
Correct |
27 ms |
55100 KB |
Output is correct |
6 |
Correct |
30 ms |
55060 KB |
Output is correct |
7 |
Correct |
29 ms |
54988 KB |
Output is correct |
8 |
Correct |
31 ms |
55008 KB |
Output is correct |
9 |
Correct |
28 ms |
55124 KB |
Output is correct |
10 |
Correct |
30 ms |
55076 KB |
Output is correct |
11 |
Correct |
28 ms |
55016 KB |
Output is correct |
12 |
Correct |
28 ms |
55048 KB |
Output is correct |
13 |
Correct |
28 ms |
55036 KB |
Output is correct |
14 |
Correct |
27 ms |
55020 KB |
Output is correct |
15 |
Correct |
29 ms |
54996 KB |
Output is correct |
16 |
Correct |
28 ms |
54996 KB |
Output is correct |
17 |
Incorrect |
31 ms |
54996 KB |
Invalid number of links. |
18 |
Halted |
0 ms |
0 KB |
- |