USACO 2019 US Open Bronze Problem 3

Problems and Contests
#1

For this problem, here is my code: 
#include <bits/stdc++.h>
using namespace std;
vector<int> tree[101];
bool visited[101];
int n, ans=-1;
int search(int node, int target){
    if(visited[node]) return -1;//checks if the node was already visited
    visited[node]=true;//since it visited it, set it to true
    if(node==target)return target;//found the target, so return the value
    for(auto next:tree[node]){
        if(search(next,target)){//recursively checks all the neighbors of a node
            return target;
        }
    }
    for(auto& ok:visited)ok=false;//sets every visit back to normal
    return -1; returns this a default because nothing was found
}
int main(){
    ifstream fin("factory.in");
    ofstream fout("factory.out");
    fin >> n;
    for(int i=0;i<n-1;i++){
        int a,b;
        fin >> a >> b;
        tree[a].push_back(b);
    }
    for(int i=1;i<n+1;i++){//this is the target node
       for(int j=1;j<n+1;j++){//checks if every node can get to the target node
            if(i!=j)ans=max(ans,search(j,i));//Think there is something wrong here but not sure
        } 
    }
    fout << ans << "\n";
}

This code works for all test cases except for the last two. I’ve tried rewriting the search function but nothing worked. Can anybody help me find any issues that may lead to this? Thanks!

#2

Could you try to give the philosophy of your solution? I can’t seem to tell what your 2 for loops (or your search function) are doing, so I can’t really help you here.

However, FWIW, I’d just brute force each of the possible nodes, seeing if the entire tree is reachable from any of them through a bfs/dfs. I assume that’s what your doing, but I can’t tell for sure.

#3

So is bronze basically about how well you can brute force a solution? Also, I’ll add some comments.

#4

I’m a bit confused about this line here:
if(search(next,target))
All the values returned in the function are nonzero, so won’t this always be true?

Also yeah, most bronze problems are brute-forcable.

1 Like
#5

I tried changing it to

if(search(next,target)!=-1)

but the I get the wrong answer for the first test case. Should I just change my approach and go brute force?

#6

Ok I solved the problem by editing my code a bit. I made it pure brute force. Thanks for your advice!

1 Like