이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 4;
int n, x, y;
int socon[3][N];
vector < int > adj[N];
int cha[3][N];
int L[N], R[N];
vector < int > path;
bool kt[N];
int dp[N];
void dfs(int i, int j, int id)
{
socon[id][i] = 1;
for (int u : adj[i])
{
if (u == j) continue;
dfs(u, i, id);
cha[id][u] = i;
socon[id][i] += socon[id][u];
}
}
bool cmp(int a, int b)
{
return dp[a] > dp[b];
}
void xuly(int i, int j, int dif)
{
vector < int > con;
for (int u : adj[i])
{
if (u == j) continue;
if (u == dif) continue;
xuly(u, i, dif);
con.push_back(u);
}
if (con.size() == 0)
{
dp[i] = 1;
return;
}
sort(con.begin(), con.end(), cmp);
for (int t = 0; t < con.size(); t++)
{
dp[i] = max(dp[i], dp[con[t]] + t + 1);
// if (i == x) cout << con[t] << " " << dp[con[t]] << '\n';
}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("t.inp","r",stdin); freopen("t.out","w",stdout);
cin >> n >> x >> y;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
kt[u] = kt[v] = false;
}
dfs(x, 0, 1);
dfs(y, 0, 2);
int node = x;
while (node != 0) {path.push_back(node); node = cha[2][node];}
int lo = 0, hi = path.size() - 2;
int res = 1e9 + 7;
if (n <= 1000)
{
for (int i = 0; i < path.size() - 1; i++)
{
xuly(x, 0, path[i + 1]);
xuly(y, 0, path[i]);
res = min(res, max(dp[x], dp[y]) - 1);
}
cout << res;
return 0;
}
// for (int u : path)
// cout << u << " ";
while (lo <= hi)
{
int mid = (lo + hi) / 2;
//cout << path[mid] << " ";
xuly(x, 0, path[mid + 1]);
xuly(y, 0, path[mid]);
res = min(res, max(dp[x], dp[y]) - 1);
//cout << dp[x] << " " << dp[y] << '\n';
if (dp[x] > dp[y]) hi = mid - 1;
else lo = mid + 1;
}
cout << res;
}
컴파일 시 표준 에러 (stderr) 메시지
torrent.cpp: In function 'void xuly(int, int, int)':
torrent.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int t = 0; t < con.size(); t++)
| ~~^~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i = 0; i < path.size() - 1; i++)
| ~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |