이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
vector<int> p, g[maxn];
int n, a, b;
bool vis[maxn];
int dp[maxn];
bool get_path(int x, int y, int p, vector<int>& P) {
if (x == y) return 1;
for (int& v : g[x]) {
if (v == p) continue;
P.emplace_back(v);
if (get_path(v, y, x, P)) return 1;
P.pop_back();
}
return 0;
}
int dfs(int x, int p=0) {
vector<int> t;
for (int v : g[x]) {
if (v == p) continue;
t.push_back(dfs(v, x));
}
sort(t.rbegin(), t.rend());
dp[x] = 0;
for (int i = 0; i < t.size(); ++i) {
dp[x] = max(dp[x], t[i] + i + 1);
}
return dp[x];
}
void remov(int x, int v) {
for (int& u : g[x]) {
if (u == v) {
swap(g[x].back(), u);
break;
}
}
g[x].pop_back();
}
int f(int t) {
remov(p[t], p[t+1]);
remov(p[t+1], p[t]);
int ans = max(dfs(a), dfs(b));
g[p[t]].emplace_back(p[t+1]);
g[p[t+1]].emplace_back(p[t]);
return ans;
}
int main() {
scanf("%d%d%d", &n, &a, &b);
for (int i = 0; i < n-1; ++i) {
int x, y;
scanf("%d%d", &x, &y);
g[x].emplace_back(y);
g[y].emplace_back(x);
}
p = {a};
get_path(a, b, 0, p);
int lo = 0, hi = p.size() - 2;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (f(mid) > f(mid+1)) lo = mid+1;
else hi = mid;
}
cout << f(lo) << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
torrent.cpp: In function 'int dfs(int, int)':
torrent.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < t.size(); ++i) {
~~^~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |