#include <bits/stdc++.h>
using namespace std;
const int mx = 3e5+5;
int n, a, b; vector<int> adj[mx], pth; bool stop = 0;
void getPath(int i, int p){
if (!stop) pth.push_back(i);
if (i == b) stop = 1;
for (int nxt : adj[i]) if (nxt != p) getPath(nxt, i);
if (!stop) pth.pop_back();
}int calc(int i, int p, int no){
vector<int> vals; int ret = 0;
for (int nxt : adj[i]) if (nxt != p and nxt != no) vals.push_back(calc(nxt, i, no));
sort(vals.begin(), vals.end(), greater<int>());
for (int x = 0; x < vals.size(); x++) ret = max(ret, vals[x]+x+1);
return ret;
}void solve(){
int low = 0, high = pth.size()-2, res = 1e9;
while (low <= high){
int mid = (low+high)/2; int x = calc(a, 0, pth[mid+1]), y = calc(b, 0, pth[mid]);
res = min(res, max(x, y));
(x < y) ? (low = mid+1) : (high = mid-1);
}cout<<res<<endl;
}
int main(){
cin >> n >> a >> b;
for (int i = 0; i < n-1; i++){
int a, b; cin >> a >> b;
adj[a].push_back(b); adj[b].push_back(a);
}getPath(a, 0); solve();
}
Compilation message
torrent.cpp: In function 'int calc(int, int, int)':
torrent.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int x = 0; x < vals.size(); x++) ret = max(ret, vals[x]+x+1);
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7344 KB |
Output is correct |
2 |
Correct |
5 ms |
7344 KB |
Output is correct |
3 |
Correct |
5 ms |
7372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
612 ms |
23224 KB |
Output is correct |
2 |
Correct |
573 ms |
24500 KB |
Output is correct |
3 |
Correct |
571 ms |
26052 KB |
Output is correct |
4 |
Correct |
588 ms |
25684 KB |
Output is correct |
5 |
Correct |
553 ms |
22580 KB |
Output is correct |
6 |
Correct |
521 ms |
23336 KB |
Output is correct |
7 |
Correct |
514 ms |
26520 KB |
Output is correct |