So, I was solving this problem and I had submitted it to the USACO grading server. I got the first 7 test cases right along with test case 13. I’m kinda confused as to what went wrong, but I don’t think it’s a fault in the logic cause it’s basically the same as the solution.
Code
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
using namespace std;
const int mxn=1e5+1;
int n,k,dist_root[mxn],parent[mxn],dist_leaf[mxn],ans=0;
vector<int> adj[mxn],leafs;
map<int,int> deg;
int main(){
cin.tie(0)->sync_with_stdio(0);
/* freopen("atlarge.in", "r", stdin); */
/* freopen("atlarge.out", "w", stdout); */
memset(dist_root,-1,sizeof(dist_root));
fill(dist_leaf,dist_leaf+mxn,INT_MAX);
cin >> n >> k;
for(int i=0;i<n-1;i++){
int a,b;cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
deg[a]++,deg[b]++;
}
//used to find which nodes are leaves
for(int i=1;i<=n;i++)
if(deg[i]==1)
leafs.push_back(i);
//find the distance for each node from the root and parent of each node
queue<int> q;q.push(k);dist_root[k]=0;
while(!q.empty()){
int top=q.front();q.pop();
for(int i:adj[top]){
if(dist_root[i]==-1){
dist_root[i]=dist_root[top]+1;
parent[i]=top;
q.push(i);
}
}
}
//find the closest leaf for each node
for(int i:leafs){
int top=i;dist_leaf[top]=0;
while(top!=k){
dist_leaf[parent[top]]=min(dist_leaf[parent[top]],dist_leaf[top]+1);
top=parent[top];
}
}
/*
if the node is farther from the root than to the closest leaf and the
the parent of the node is closer to the root than to the closest leaf,
then we need an extra farmer
*/
for(int i=1;i<=n;i++)
if(dist_root[parent[i]]<dist_leaf[parent[i]]&&dist_root[i]>=dist_leaf[i])
ans++;
cout << ans << "\n";
}
Can someone give me a hint as to what went wrong? Thanks!!
