이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
template <typename T>
using ve = vector<T>;
int main() {
int n;
scanf("%d", &n);
ve<ve<int> > g(n);
for (int u, v, i = 1; i < n; ++i)
scanf("%d%d", &u, &v), --u, --v, g[u].push_back(v), g[v].push_back(u);
auto dfs = [&](auto dfs, int u, int p, ve<int> &dep) -> void {
for (auto v : g[u]) if (v != p) dep[v] = dep[u] + 1, dfs(dfs, v, u, dep);
};
ve<int> dep(n), eep(n);
dfs(dfs, 0, 0, dep);
int a = (int)(max_element(dep.begin(), dep.end()) - dep.begin());
dep.assign(n, 0);
dfs(dfs, a, a, dep);
int b = (int)(max_element(dep.begin(), dep.end()) - dep.begin());
dfs(dfs, b, b, eep);
auto lik = [&](int i) { return dep[i] + eep[i] == eep[a]; };
ve<int> pat;
for (int i = 0; i < n; ++i) if (lik(i)) pat.push_back(i);
sort(pat.begin(), pat.end(), [&](int i, int j){ return dep[i] < dep[j]; });
ve<int> ww(n, 1);
auto efs = [&](auto efs, int u, int p, int rt) -> void {
++ww[rt];
for (auto v : g[u]) if (p != v && !lik(v)) efs(efs, v, u, rt);
};
for (auto x : pat) for (auto y : g[x]) if (!lik(y)) efs(efs, y, y, x);
int l = 0, r = (int)pat.size() - 1, ls = 0, rs = 0;
for (int i = 1; i <= n; ++i) {
if (i & 1) puts("1");
else {
while (ls < i / 2 && l < (int)pat.size()) {
ls += ww[pat[l++]];
}
while (rs < i / 2 && r >= 0) {
rs += ww[pat[r--]];
}
printf("%d\n", max(1, (r + 1) - (l - 1) + 1));
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
meetings2.cpp: In function 'int main()':
meetings2.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
meetings2.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | scanf("%d%d", &u, &v), --u, --v, g[u].push_back(v), g[v].push_back(u);
| ~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |