| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 254863 | 2020-07-30T18:34:12 Z | dolphingarlic | Village (BOI20_village) | C++14 | 140 ms | 16952 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 100000;
int n;
struct Vertex{
vector<int> to;
int sz;
}v[MAXN + 1];
ll smallest_distance, largest_distance;
int place_smallest[MAXN + 1];
int place_largest[MAXN + 1];
int group[MAXN + 1];
int groupsz[MAXN + 1];
int order[MAXN + 1];
int cnt[MAXN + 1];
void dfs(int it, int p = 0)
{
v[it].sz = 1;
for (auto t : v[it].to)
{
if (t == p)
continue;
dfs(t, it);
v[it].sz += v[t].sz;
}
if (place_smallest[it] == it)
{
smallest_distance += 2;
if (p != 0)
{
swap(place_smallest[it], place_smallest[p]);
}
else
{
swap(place_smallest[it], place_smallest[v[it].to.front()]);
}
}
}
int get_centroid()
{
int it = 1;
while (true)
{
int nxt = 0;
for (auto t : v[it].to)
{
if (v[t].sz > v[it].sz)
continue;
if (v[t].sz * 2 > n)
{
nxt = t;
break;
}
}
if (nxt == 0)
break;
it = nxt;
}
return it;
}
int nextGroup = 0;
void dfsGroup(int it)
{
group[it] = nextGroup;
for (auto t : v[it].to)
{
if (group[t] != 0)
continue;
dfsGroup(t);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int a, b;
scanf("%d %d", &a, &b);
v[a].to.push_back(b);
v[b].to.push_back(a);
}
for (int i = 1; i <= n; i++)
place_smallest[i] = i;
dfs(1);
for (int i = 1; i <= n; i++)
{
largest_distance += 2 * min(v[i].sz, n - v[i].sz);
}
int centroid = get_centroid();
group[centroid] = ++nextGroup;
for (auto t : v[centroid].to)
{
++nextGroup;
dfsGroup(t);
}
for (int i = 1; i <= n; i++)
{
groupsz[group[i]]++;
}
for (int i = 1; i <= nextGroup; i++)
{
groupsz[i] += groupsz[i - 1];
}
for (int i = 1; i <= n; i++)
{
order[groupsz[group[i] - 1] + cnt[group[i]]++] = i;
}
for (int i = 0, j = n / 2; i < n; i++, j++)
{
if (j >= n)
j = 0;
place_largest[order[i]] = order[j];
}
printf("%lld %lld\n", smallest_distance, largest_distance);
for (int i = 1; i <= n; i++)
printf("%d ", place_smallest[i]);
printf("\n");
for (int i = 1; i <= n; i++)
printf("%d ", place_largest[i]);
printf("\n");
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 3456 KB | Output is correct |
| 2 | Correct | 3 ms | 3456 KB | Output is correct |
| 3 | Correct | 2 ms | 3456 KB | Output is correct |
| 4 | Correct | 2 ms | 3456 KB | Output is correct |
| 5 | Correct | 2 ms | 3456 KB | Output is correct |
| 6 | Correct | 2 ms | 3456 KB | Output is correct |
| 7 | Correct | 3 ms | 3456 KB | Output is correct |
| 8 | Correct | 2 ms | 3456 KB | Output is correct |
| 9 | Correct | 2 ms | 3456 KB | Output is correct |
| 10 | Correct | 2 ms | 3456 KB | Output is correct |
| 11 | Correct | 3 ms | 3456 KB | Output is correct |
| 12 | Correct | 2 ms | 3456 KB | Output is correct |
| 13 | Correct | 2 ms | 3456 KB | Output is correct |
| 14 | Correct | 2 ms | 3456 KB | Output is correct |
| 15 | Correct | 3 ms | 3456 KB | Output is correct |
| 16 | Correct | 3 ms | 3456 KB | Output is correct |
| 17 | Correct | 4 ms | 3456 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 3456 KB | Output is correct |
| 2 | Correct | 5 ms | 3456 KB | Output is correct |
| 3 | Correct | 3 ms | 3456 KB | Output is correct |
| 4 | Correct | 4 ms | 3584 KB | Output is correct |
| 5 | Correct | 3 ms | 3584 KB | Output is correct |
| 6 | Correct | 3 ms | 3584 KB | Output is correct |
| 7 | Correct | 3 ms | 3584 KB | Output is correct |
| 8 | Correct | 3 ms | 3584 KB | Output is correct |
| 9 | Correct | 3 ms | 3584 KB | Output is correct |
| 10 | Correct | 3 ms | 3584 KB | Output is correct |
| 11 | Correct | 3 ms | 3584 KB | Output is correct |
| 12 | Correct | 3 ms | 3584 KB | Output is correct |
| 13 | Correct | 3 ms | 3584 KB | Output is correct |
| 14 | Correct | 3 ms | 3584 KB | Output is correct |
| 15 | Correct | 3 ms | 3584 KB | Output is correct |
| 16 | Correct | 3 ms | 3584 KB | Output is correct |
| 17 | Correct | 3 ms | 3584 KB | Output is correct |
| 18 | Correct | 3 ms | 3584 KB | Output is correct |
| 19 | Correct | 3 ms | 3584 KB | Output is correct |
| 20 | Correct | 3 ms | 3584 KB | Output is correct |
| 21 | Correct | 2 ms | 3584 KB | Output is correct |
| 22 | Correct | 3 ms | 3584 KB | Output is correct |
| 23 | Correct | 3 ms | 3584 KB | Output is correct |
| 24 | Correct | 3 ms | 3456 KB | Output is correct |
| 25 | Correct | 2 ms | 3456 KB | Output is correct |
| 26 | Correct | 3 ms | 3584 KB | Output is correct |
| 27 | Correct | 2 ms | 3456 KB | Output is correct |
| 28 | Correct | 3 ms | 3584 KB | Output is correct |
| 29 | Correct | 3 ms | 3584 KB | Output is correct |
| 30 | Correct | 3 ms | 3584 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 3456 KB | Output is correct |
| 2 | Correct | 3 ms | 3456 KB | Output is correct |
| 3 | Correct | 2 ms | 3456 KB | Output is correct |
| 4 | Correct | 2 ms | 3456 KB | Output is correct |
| 5 | Correct | 2 ms | 3456 KB | Output is correct |
| 6 | Correct | 2 ms | 3456 KB | Output is correct |
| 7 | Correct | 3 ms | 3456 KB | Output is correct |
| 8 | Correct | 2 ms | 3456 KB | Output is correct |
| 9 | Correct | 2 ms | 3456 KB | Output is correct |
| 10 | Correct | 2 ms | 3456 KB | Output is correct |
| 11 | Correct | 3 ms | 3456 KB | Output is correct |
| 12 | Correct | 2 ms | 3456 KB | Output is correct |
| 13 | Correct | 2 ms | 3456 KB | Output is correct |
| 14 | Correct | 2 ms | 3456 KB | Output is correct |
| 15 | Correct | 3 ms | 3456 KB | Output is correct |
| 16 | Correct | 3 ms | 3456 KB | Output is correct |
| 17 | Correct | 4 ms | 3456 KB | Output is correct |
| 18 | Correct | 3 ms | 3456 KB | Output is correct |
| 19 | Correct | 5 ms | 3456 KB | Output is correct |
| 20 | Correct | 3 ms | 3456 KB | Output is correct |
| 21 | Correct | 4 ms | 3584 KB | Output is correct |
| 22 | Correct | 3 ms | 3584 KB | Output is correct |
| 23 | Correct | 3 ms | 3584 KB | Output is correct |
| 24 | Correct | 3 ms | 3584 KB | Output is correct |
| 25 | Correct | 3 ms | 3584 KB | Output is correct |
| 26 | Correct | 3 ms | 3584 KB | Output is correct |
| 27 | Correct | 3 ms | 3584 KB | Output is correct |
| 28 | Correct | 3 ms | 3584 KB | Output is correct |
| 29 | Correct | 3 ms | 3584 KB | Output is correct |
| 30 | Correct | 3 ms | 3584 KB | Output is correct |
| 31 | Correct | 3 ms | 3584 KB | Output is correct |
| 32 | Correct | 3 ms | 3584 KB | Output is correct |
| 33 | Correct | 3 ms | 3584 KB | Output is correct |
| 34 | Correct | 3 ms | 3584 KB | Output is correct |
| 35 | Correct | 3 ms | 3584 KB | Output is correct |
| 36 | Correct | 3 ms | 3584 KB | Output is correct |
| 37 | Correct | 3 ms | 3584 KB | Output is correct |
| 38 | Correct | 2 ms | 3584 KB | Output is correct |
| 39 | Correct | 3 ms | 3584 KB | Output is correct |
| 40 | Correct | 3 ms | 3584 KB | Output is correct |
| 41 | Correct | 3 ms | 3456 KB | Output is correct |
| 42 | Correct | 2 ms | 3456 KB | Output is correct |
| 43 | Correct | 3 ms | 3584 KB | Output is correct |
| 44 | Correct | 2 ms | 3456 KB | Output is correct |
| 45 | Correct | 3 ms | 3584 KB | Output is correct |
| 46 | Correct | 3 ms | 3584 KB | Output is correct |
| 47 | Correct | 3 ms | 3584 KB | Output is correct |
| 48 | Correct | 78 ms | 8952 KB | Output is correct |
| 49 | Correct | 103 ms | 9592 KB | Output is correct |
| 50 | Correct | 107 ms | 9592 KB | Output is correct |
| 51 | Correct | 72 ms | 8184 KB | Output is correct |
| 52 | Correct | 88 ms | 9464 KB | Output is correct |
| 53 | Correct | 99 ms | 8824 KB | Output is correct |
| 54 | Correct | 45 ms | 9976 KB | Output is correct |
| 55 | Correct | 120 ms | 16952 KB | Output is correct |
| 56 | Correct | 140 ms | 12920 KB | Output is correct |
| 57 | Correct | 133 ms | 11728 KB | Output is correct |
| 58 | Correct | 115 ms | 10616 KB | Output is correct |
| 59 | Correct | 108 ms | 9592 KB | Output is correct |
| 60 | Correct | 75 ms | 10480 KB | Output is correct |
| 61 | Correct | 71 ms | 9976 KB | Output is correct |
| 62 | Correct | 86 ms | 9848 KB | Output is correct |
| 63 | Correct | 71 ms | 9464 KB | Output is correct |
| 64 | Correct | 79 ms | 9848 KB | Output is correct |
| 65 | Correct | 94 ms | 9976 KB | Output is correct |
| 66 | Correct | 71 ms | 9468 KB | Output is correct |
| 67 | Correct | 52 ms | 8184 KB | Output is correct |
| 68 | Correct | 64 ms | 8952 KB | Output is correct |
| 69 | Correct | 75 ms | 9976 KB | Output is correct |
| 70 | Correct | 69 ms | 9592 KB | Output is correct |
| 71 | Correct | 49 ms | 8056 KB | Output is correct |
| 72 | Correct | 55 ms | 8572 KB | Output is correct |
| 73 | Correct | 75 ms | 9976 KB | Output is correct |
| 74 | Correct | 67 ms | 9336 KB | Output is correct |
| 75 | Correct | 105 ms | 9336 KB | Output is correct |
| 76 | Correct | 111 ms | 9320 KB | Output is correct |
| 77 | Correct | 76 ms | 9592 KB | Output is correct |
| 78 | Correct | 56 ms | 7544 KB | Output is correct |
| 79 | Correct | 86 ms | 8184 KB | Output is correct |
| 80 | Correct | 85 ms | 9336 KB | Output is correct |
| 81 | Correct | 98 ms | 9724 KB | Output is correct |
| 82 | Correct | 82 ms | 9720 KB | Output is correct |