This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N = 1e6 + 5;
int n, m, t;
int w[N], P[N];
vector<int> gr[N];
vector<pair<int,int>> L;
vector<int> path;
void dfs(int x, int p){
P[x] = p;
for(auto to : gr[x]){
if(to == p) continue;
dfs(to, x);
}
}
int CNT;
void count_w(int x, int cnt, int dep){
if(gr[x].size() == 1){
w[x] = cnt + dep;
return ;
}
cnt += gr[x].size() - 2;
vector<int>v;
for(int to : gr[x]){
if(to == P[x]) continue;
count_w(to, cnt, dep+1);
v.pb(w[to]);
}
cnt -= gr[x].size() - 2;
sort(v.rbegin(),v.rend());
if(v.size() == 1){
w[x] = 1 + dep + cnt;
} else {
w[x] = v[1];
}
}
inline bool check(int x){
int B = 0;
for(int i = 0; i < L.size(); i++){
auto p = L[i];
//if(i == L.size() - 1) return p.ss + B <= x;
if(B >= p.ff){
if(p.ss + B > x) return false;
} else
if(p.ss + B > x){
B++;
}
if(B > x) return false;
}
return true;
}
int main(){
cin >> n >> t >> m;
for(int i = 1; i < n; i++){
int x, y;
cin >> x >> y;
gr[x].pb(y);
gr[y].pb(x);
}
dfs(t,0);
int ver = m;
while(ver != t){
path.pb(ver);
ver = P[ver];
}
reverse(path.begin(), path.end());
for(int i = 0; i < path.size(); i++){
int x = path[i];
int k = 3;
if(i == path.size() - 1) k--;
CNT += max(0, (int)gr[x].size() - k);
//cout << CNT << endl;
for(int to : gr[x]){
if(to == P[x]) continue;
if(path.size() - 1 != i && to == path[i+1]) continue;
count_w(to, CNT, 1);
L.pb({path.size() - i, w[to]});
}
if((int)gr[x].size() >= 3)CNT++;
}
//for(int i = 1; i <= n; i++) cout << w[i] << " "; cout << endl;
sort(L.begin(), L.end());
//for(auto p : L) cout << p.ff << " " << p.ss << endl;
int l = 0, r = 1e6, answer = -1;
while(l <= r) {
int mid = l+r; mid >>= 1;
if(check(mid)){
answer = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << answer << endl;
}
Compilation message (stderr)
mousetrap.cpp: In function 'bool check(int)':
mousetrap.cpp:50:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < L.size(); i++){
~~^~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:86:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < path.size(); i++){
~~^~~~~~~~~~~~~
mousetrap.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == path.size() - 1) k--;
~~^~~~~~~~~~~~~~~~~~
mousetrap.cpp:94:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(path.size() - 1 != i && to == path[i+1]) continue;
~~~~~~~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |