이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <queue>
#include <cstdio>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
const int MAX = 100006;
int n, maxDepth[MAX], depth[MAX], childs[MAX], sz[MAX];
vector<int> adj[MAX], c[MAX];
int nextShort[MAX], e[MAX], resShort;
int nextLong[MAX];
long long resLong;
bool visited[MAX];
vector<int> tmp[MAX];
int tok[MAX];
int dfs(int x, int prev = -1) {
sz[x] = 1;
for (auto &i: adj[x]) if (i != prev) {
c[x].push_back(i);
sz[x] += dfs(i, x);
}
return sz[x];
}
int centroid(int x, int prev = -1) {
for (auto &i: adj[x]) if (i != prev && sz[i] > n / 2) return centroid(i, x);
return x;
}
void dfsShort(int x) {
e[x] = x;
vector<int> zero;
for (auto &i: c[x]) {
if (!childs[i]) zero.push_back(i), e[x] = i;
else {
dfsShort(i);
if (childs[i]) childs[x]--;
else zero.push_back(i), e[x] = i;
}
}
if (!childs[x]) return;
if (zero.empty()) return;
nextShort[x] = zero[0];
for (int i = 0; i < (int)zero.size(); i++) {
if (i != (int)zero.size() - 1) nextShort[zero[i]] = zero[i + 1];
else nextShort[zero[i]] = x;
resShort += 2;
}
}
void depthFrom(int x, int prev = -1) {
maxDepth[x] = depth[x];
for (auto &i: adj[x]) if (i != prev && !visited[i]) {
depth[i] = depth[x] + 1;
depthFrom(i, x);
maxDepth[x] = max(maxDepth[x], maxDepth[i]);
}
}
pair<int, int> farthest(int x, int prev = -1) {
for (auto &i: adj[x]) if (i != prev && !visited[i]) {
if (maxDepth[i] == maxDepth[x]) {
pair<int, int> t = farthest(i, x);
return { t.first, t.second + 1 };
}
}
return { x, 0 };
}
void fl(int x, int prev, vector<int> &f) {
f.push_back(x);
for (auto &i: adj[x]) if (i != prev) fl(i, x, f);
}
int main() {
scanf("%d", &n);
fill(nextShort, nextShort + n, -1);
for (int i = 0; i < n - 1; i++) {
int u, v;
scanf("%d%d", &u, &v);
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0);
int ct = centroid(0);
for (int i = 0; i < n; i++) childs[i] = (int)c[i].size();
dfsShort(0);
if (nextShort[0] == -1) {
nextShort[0] = c[0][0];
nextShort[e[c[0][0]]] = 0;
resShort += 2;
}
for (int i = 0; i < n; i++) c[i].clear();
dfs(ct);
depth[ct] = 0;
depthFrom(ct);
vector<pair<int, int>> v;
for (auto &i: adj[ct]) v.push_back({ sz[i], i });
sort(v.begin(), v.end());
swap(v.front(), v.back());
int remainSum = 0;
for (int i = 1; i < (int)v.size(); i++) remainSum += v[i].first;
queue<pair<int, int>> q;
vector<pair<int, int>> u;
for (auto &i: adj[ct]) if (i != v[0].second) u.push_back({ i, sz[i] });
vector<int> res;
for (auto &i: u) q.push(i);
while (!q.empty()) {
auto t = q.front(); q.pop();
if (!t.second) continue;
t.second--;
res.push_back(t.first);
q.push(t);
}
int k = 0;
vector<int> r;
while (remainSum > v[0].first) {
r.push_back(res[k++]);
remainSum--;
}
while (v[0].first) {
r.push_back(v[0].second);
v[0].first--;
if (remainSum) r.push_back(res[k++]), remainSum--;
}
for (int i = 0; i < (int)v.size(); i++) fl(v[i].second, ct, tmp[v[i].second]);
vector<int> fin;
for (auto &i: r) {
resLong += depth[tmp[i][tok[i]]] * 2;
fin.push_back(tmp[i][tok[i]++]);
}
for (int i = 0; i < n - 2; i++) nextLong[fin[i]] = fin[i + 1];
nextLong[fin[n - 2]] = ct;
nextLong[ct] = fin[0];
printf("%d %lld\n", resShort, resLong);
for (int i = 0; i < n; i++) printf("%d ", nextShort[i] + 1);
puts("");
for (int i = 0; i < n; i++) printf("%d ", nextLong[i] + 1);
}
컴파일 시 표준 에러 (stderr) 메시지
Village.cpp: In function 'int main()':
Village.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
80 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
Village.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |